《可计算性与不可解性》求取 ⇩

第一部分　可计算性的一般理论14

第一章　可计算函数14

1．图林机14

2．可计算函数和部分可计算函数21

3．一些例子25

4．相对可计算函数37

第二章　可计算函数上的运算43

1．预备引理43

2．复合与取极小58

第三章　递归函数65

1．一些函数类65

2．自然数的有穷序列68

3．原始递归性72

4．原始递归函数76

5．递归的集合和谓词79

1．图林机理论的算术化84

第四章　作用于自身的图林机84

2．可计算性与递归性92

3．一种通用图林机94

第五章　不可解的判定问题96

1．半可计算谓词96

2．判定问题100

3．半可计算谓词的性质103

4．递归可枚举集105

5．两个递归可枚举集108

6．不是递归可枚举的集合111

第二部分　一般理论的应用113

第六章　组合问题113

1．组合问题113

2．图林机和半图厄系统122

3．图厄系统130

4．半群的字的问题132

5．正规系统和波斯特系统137

1．希尔伯特第十问题141

第七章　刁番图方程141

2．算术谓词和刁番图谓词142

3．半可计算谓词的算术表示148

第八章　数理逻辑161

1．逻辑161

2．逻辑的不完全性定理和不可解性定理165

3．算术逻辑168

4．一阶逻辑179

5．部分命题演算190

第三部分　一般理论的进一步发展197

第九章　KLEENE层次197

1．迭代定理197

2．迭代定理的一些初步应用202

3．谓词、集合和函数204

4．强归约性206

5．某些谓词类208

6．P？表示定理212

7．Post表示定理216

第十章　可计算泛函220

1．泛函220

2．完全可计算泛函223

3．范式定理226

4．部分可计算泛函与可计算泛函228

5．泛函与相对递归性230

6．判定问题232

7．递归定理236

第十一章　不可判定问题的分类242

1．可归约性和K1eene层次242

2．不可比较性244

3．创造集与单纯集248

4．构造性序数251

5．Kleene层次的扩张257

附录　初等数论中的某些结果261

参考文献269