第1章 计算的对象和本质 1
参考文献 6
第2章 可计算函数——递归函数 7
2.1 分解计算、逐步计算的思想 8
2.2 原始函数 10
2.3 递归函数的构造方法 11
2.3.1 复合方法 12
2.3.2 递归方法 12
2.4 递归函数的家族 21
2.5 递归函数的通俗解释 22
参考文献 23
第3章 计算机的数学原理 25
3.1 数学运算的基础 25
3.2 希尔伯特第十个问题及其自动化解决思想 28
3.3 图灵机原理 32
3.4 图灵机的局部改进和变形 50
3.4.1 多带图灵机 50
3.4.2 图灵机的复合 53
3.4.3 图灵机参数的限定 57
参考文献 57
第4章 语言的计算 59
4.1 图灵计算的分类 59
4.2 语言的可计算性 61
4.3 作为枚举器的图灵机 69
4.4 作为语言识别器（接受器）的图灵机 70
4.5 图灵机和短语语法 72
4.6 线性有界自动机与上下文有关语法 77
4.7 下推自动机与上下文无关语法 83
4.8 确定型有穷自动机与正则语法 86
4.9 不确定型有穷自动机与正则语法 89
4.10 自动机接受的语言 94
参考文献 95
第5章 判定问题的可计算性 97
5.1 基本概念 97
5.2 不可判定性问题实例 98
5.2.1 丢番图方程整数解问题 99
5.2.2 对角线函数 102
5.2.3 停机问题 104
5.2.4 逻辑蕴涵 106
5.2.5 哥德尔语句G 109
参考文献 110
第6章 计算模型的应用 112
6.1 计算机模拟图灵机 112
6.2 语言识别和语法验证 115
6.3 逻辑推理 123
6.4 计算复杂性分析 133
参考文献 139