《可计算性理论》求取 ⇩

引论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

(二)URM211

(三)算子算法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