计算理论与符号逻辑

.习题
第4章图灵可计算性
4.1能行可计算
4.2图灵可计算性
4.3图灵机的例子
4.4图灵机的多种表示方法
4.4.1状态图表示法
4.4.2状态转换表表示法
4.4.3元组表示法
4.5对定义4.2的进一步讨论
4.6不可计算性
4.6.1图灵不可计算函数的存在性
4.6.2对角线函数的构造
4.6.3停机函数的引入
4.6.4停机函数图灵不可计算性的直接证明
4.7图灵论题与通用图灵机
习题
第5章算盘可计算性
5.1算盘机的定义
5.2算盘机例子程序
5.3算盘可计算性
5.4将算盘机编译为图灵机
5.4.1算盘机内存在读写带上的表示
5.4.2算盘机程序的编译方法
习题
第6章递归函数可计算性
6.1递归函数的引入
6.2基本函数
6.3递归算子
6.3.1复合算子
6.3.2原始递归算子
6.4递归函数与函数式程序设计
6.5一般递归算子
6.6递归函数的定义
6.7将递归函数编译为算盘机
6.7.1基本函数的编译
6.7.2cn的编译，以cn【f，g1，g1】为例
6.7.3pr的编译
6.7.4mn的编译
习题
第7章递归函数与递归关系
7.1递归集合和递归关系
7.2基于递归集合和递归关系的程序设计
7.3半递归集合和半递归关系
7.4小结
习题
第8章不同计算模型之间的等价性
8.1读写带的表示
8.2图灵机动作的表示
8.3图灵机程序的表示
8.4图灵机配置及执行过程的表示
8.5图灵机停机条件与计算结果的提取
8.6图灵机解释函数的构诰
8.7关于可计算性的一组重要结论
8.8第一部分总结与后续部分的引入
习题
第9章一阶谓词逻辑的基本概念
9.1符号逻辑的引入
9.2符号、语言、公式、项和解释
9.3一阶谓词逻辑语法的定义
9.4正式写法与常用写法对应关系举例
9.5解释与语义
9.6蕴涵关系与逻辑推理
9.7可满足性原理与蕴涵关系的半可判定过程
9.8小结
习题
第10章蕴涵关系的不可判定性
10.2γ的构造
10.2.1γb的构造
10.2.2γi的构造
10.2.3γp的构造
10.2.4d的构造
10.3主定理的证明
习题
第11章模型
11.1模型及其尺寸
11.2同构与模型的数量
11.3等价关系
11.4lowenheim-skolem定理和紧致性定理
11.5非标准模型
11.6小结
习题
第12章紧致性定理的证明
12.1获得一个被彻底分解的句子集合
12.1.1足够多的空闲常量
12.1.2用覆盖来刻画“彻底分解”
12.1.3获取己彻底分解集合γ的过程
12.2为γ*构造模型
12.3证明的总体结构
习题
第13章形式化推理系统
13.1矢列演算及其合理性
13.2用矢列演算进行推理的例子
13.3矢列演算的完备性
13.4矢列演算小结
13.5算术化与一阶谓词逻辑的计算机实现
13.6什么是理想的数学理论
13.7小结
习题
第14章计算行为的逻辑刻画
14.1递归函数算术可定义性
14.1.1算术可定义性
14.1.2递归函数的算术可定义性
14.1.3递归函数的初步性
14.2递归函数的可表示性
14.2.1函数的可表示性
14.2.2最小算术理论q
14.2.3递归函数在q中的可表示性
14.3小结
习题
第15章godel不完全性定理
15.1对角线引理与godel第一不完全性定理.
15.2不可判定的句子
15.3godel第一不完全性定理小结
15.4godel第二不完全性定理
15.5lob定理的证明
15.6小结与历史回顾
习题
参考文献
索引