引论 1
(一)计算及可计算性 1
(二)可计算性理论的发展 3
(三)G？del 编号 5
(四)本书内容简介 10
第一章 递归函数 13
第一节 原始递归函数 15
1.1 原始递归函数 16
(一)原始递归函数的定义 16
(二)原始递归函数的运算 20
1.2 原始递归谓词 23
(一)原始递归谓词的定义 23
(二)原始递归谓词的运算 27
1.3 原始递归函数的其它定义 29
(一)递归与迭代 29
(二)一元原始递归函数 34
(一)多步递归 37
1.4 关于递归运算 37
(二)多变元递归 39
(三)联立递归 41
(四)嵌套递归 42
第二节 递归函数 42
1.5 μ递归函数及递归谓词 43
(一)μ递归函数的定义 43
(二)递归谓词 46
(三)G？del β函数 48
(四)利用μ运算消去递归运算 50
1.6 Ackermann 函数 52
1.7 一般递归函数 61
1.8 μ递归函数与一般递归函数 67
第三节 递归可枚举集及递归集 79
1.9 递归可枚举集 80
(一)递归可枚举集 80
(二)递归可枚举集的运算 81
(三)递归函数的图形定理 83
(一)原始递归集及递归集 89
1.10 递归集 89
(二)原始递归集及递归集的运算 92
(三)递归集与递归可枚举集的关系 93
1.11 递归可枚举谓词 98
第四节 通用函数、递归定理 103
1.12 Kleene 法式定理、通用函数 104
(一)Kleene 法式定理 105
(二)原始递归函数的通用函数 107
(三)递归函数的通用函数、枚举定理 111
1.13 s-m-n 定理、递归定理 113
(一)递归函数的G？del 编号 113
(二)S-m-n 定理 118
(三)递归定理 120
1.14 关于集合及谓词的若干性质 122
(一)递归可枚举集的编号 122
(二)谓词的 Kleene-Mostowski 分层 126
1.15 递归字函数的算术化定义 133
(一)字的算术化 133
第五节 字函数 133
(二)递归的字集及字函数 136
1.16 递归字函数的直接定义 138
(一)直接定义 139
(二)直接定义等价于算术化定义 143
第二章 Turing 机 149
2.1 Turing 机的概念 151
(一)Turing 机及其计算 151
第一节 Turing 机的基本概念 151
(二)Turing 机计算及符号变换 157
(三)Turing 机的四元组指令 159
2.2 Turing 机的标准化及组合 162
(一)Turing 机的标准化 162
(二)Turing 机的组合 167
第二节 Turing 可计算函数 168
2.3 递归函数是 Turing 可计算函数 168
2.4 Turing 可计算函数是递归函数 180
2.5 通用 Turing 机 186
(一)通用 Turing 机 186
第三节 通用 Turing 机 186
(二)Turing 机的枚举 192
2.6 关于小的通用 Turing 机 192
第四节 Turing 机的变形 197
2.7 多头多带 Turing 机 198
(一)半无限带的 Turing 机 199
(二)多读写头的 Turing 机 201
(三)多带 Turing 机 204
(一)W 机 205
2.8 W 机、URM 及算子算法 205
(二)URM 211
(三)算子算法 216
2.9 Minsky 机 218
(一)Minsky 机与算子算法 218
(二)三带 Minsky 机 220
(三)二带 Minsky 机 223
第五节 递归函数的子类 227
(一)Grzegorczyk 层次 228
2.10 原始递归函数的层次 228
(二)初等函数 231
2.11 初等函数的层次 233
(一)基本概念 233
(二)函数类？ 237
(三)函数类？ 242
2.12 可计算函数的复杂性类 243
(一)计算复杂性的尺度 244
(二)复杂性类 248
(三)分层问题 250
第三章 Post 系统 255
第一节 半 Thue 系统及 Thue 系统 256
3.1 半 Thue 系统及 Thue 系统 256
(一)半 Thue 系统 256
(二)Thue 系统 259
3.2 半 Thue 系统与可计算性 260
(一)Turing 机可计算是半 Thue 系统可计算 260
(二)半 Thue 系统的字集合与递归可枚举集 262
第二节 Post 系统 264
3.3 正规系统 265
3.4 tag 系统 268
3.5 标准系统 276
(一)标准系统 276
(二)标准系统与正规系统 278
第三节 马尔科夫算法 288
3.6 马尔科夫算法 289
(一)马尔科夫算法的基本概念 289
(二)马尔科夫算法的组合 292
3.7 马尔科夫算法与递归函数 299
第四章 判定问题 305
第一节 基本概念 306
4.1 判定问题的基本概念 306
(一)历史背景 306
(二)基本定义 308
(三)基本方法 310
4.2 非递归函数的例子 310
4.3 Turing 机的停机问题 314
(一)停机问题 314
第二节 若干递归不可解的判定问题 314
(二)Turing 机的完全性及等价性 315
4.4 字问题及 Post 对应问题 319
(一)半 Thue 系统及正规系统的字问题 319
(二)Thue 系统的字问题 321
(三)Post 对应问题 322
第三节 不可解级 326
4.5 相对递归及 Turing 级 327
(一)相对递归 327
(二)带有解算装置的 Turing 机 329
(三)Turing 归约及 Turing 级 330
4.6 (m，1)级及(1，1)级 333
(一)(m，1)归约及(m，1)级 333
(二)(1，1)归约及(1，1)级 337
4.7 递归可枚举级 338
(一)创造集及生产集 338
(二)完全集 342
(三)简单集及禁集 344
参考文献 348