计算理论PDF电子书下载

第一章　关于数学基础问题 1

1.1 数集和数系 1

1.1.1 数学的严格化运动 1

1.1.2 自然数和有理数的结构 3

1.1.3 实数系的逻辑结构 5

1.1.4　无理数 8

1.2 一般集合的逻辑结构 9

1.2.1 关于现实无穷集合是否存在的问题 2

1.2.2 康托尔朴素集合论 10

1.2.3 基数和序数 11

1.2.4 超限基数和超限序数 12

1.2.5 集合论中可靠思维的范围 14

1.2.6 集合论中的悖论 15

1.3 关于数学基础问题的几个学说 16

1.3.1 逻辑派的基本思想 16

1.3.2　直观主义者 18

1.3.3　形式主义学派 19

第二章　形式系统 22

2.1 公理及谓词逻辑的解释系统 22

2.1.1　关于公理方法 23

2.1.2 公理系统及寓于其中的常量符号 24

2.1.3 公理系统的实质无矛盾性、独立性和完全性 26

2.1.4 自然序列公理 29

2.2 形式系统 31

2.2.1 问题本身的启示 32

2.2.2 对象系统的构形 33

2.2.3 可构造类和可构造运算 34

2.2.4 形式系统的定义 36

2.2.5 形式系统中无矛盾性问题的例 36

2.2.6 希尔伯特方案的主要问题 17

2.3 谓词演算——形式系统的例 38

2.3.1 谓词演算系统的构造性 39

2.3.2 谓词演算的无矛盾性问题 41

2.3.3 狭义完全性 43

2.3.4 演绎等价和广义完全性 44

第三章　递归函数论 46

3.1 数字函数及其作用于它的基本语句 46

3.1.1 函数和项 46

3.1.2 基本可计算语句 47

3.1.3 一些初等算术函数的原始递归性 49

3.1.4 最小化语句 51

3.1.5 递归集 52

3.1.6　一般递归函数 53

3.1.7 递归谓词 53

3.2 原始递归函数 54

3.2.1 关于某些数字函数的原始递归性 55

3.2.2　n-元组的枚举 61

3.2.3　单目原始递归函数 66

3.3　递归可枚举集 70

3.3.1　递归可枚举集 70

3.3.2　表达集 73

3.3.3　n-元自然数串集 74

3.4　一般递归函数 77

3.4.1　二阶递归 77

3.4.2　通用一般递归函数 80

3.4.3　快速上升函数 84

3.5　部分递归函数 88

3.5.1　部分递归函数的参量化 88

3.5.2　通用部分递归函数和非递归的递归可枚举集 91

3.5.3　克林表达式 94

第四章　字递归函数 97

4.1　字代数 97

4.1.1　字集和字函数 97

4.1.2　正则表达式 98

4.1.3　字代数系统 100

4.2　字递归函数 102

4.2.1　字集的枚举，表达函数 102

4.2.2　基本字语句 104

4.2.3　字部分递归函数的直接定义 108

4.2.4　字递归函数的实例·字递归谓词 110

第五章　计算的理论模型 113

5.1　计算的直观理解 113

5.1.1　直观计算概念的几个要点 113

5.1.2　数值计算 114

5.1.3　博奕计算 116

5.1.4　图的计算 118

5.2　一些计算问题 120

5.2.1　代数系统和结合律演算中的字等价问题 120

5.2.2　一阶逻辑公式的永真性判定问题 122

5.2.3　算术集合和算术函数 123

5.3　形式语言与自动机 125

5.3.1　形式语言的文法 125

5.3.2　有穷自动机 127

5.3.3　下推自动机 130

5.4 图灵机和图灵可计算 134

5.4.1　图灵-波斯特机 134

5.4.2　图灵可计算函数 137

5.4.3　图灵机的设计 140

5.4.4　图形定理和通用部分递归函数的存在性 148

第六章　命数论基础 152

6.1 集合和函数集的枚举 152

6.1.1　克林命数 152

6.1.2　波斯特命数 155

6.1.3　单值命数 158

6.2　集合的归约性和创造性 161

6.2.1　集合的归约性和m-等价性 161

6.2.2　产生集和创造性 163

6.2.3　简单集和最大集 165

6.3　任意集合的命数 169

6.3.1　命数的同构性和等价性 169

6.3.2　命数的单归约性 171

6.3.3　完全命数 175

6.3.4　被命数集合的子集合 178

6.4　通用和创造的集合系列 179

6.4.1　m-通用集合系列 179

6.4.2　创造的集合系列 182

6.4.3　递归非分离集 184

第七章　一些其它的计算模型和计算问题 186

7.1　一些计算问题 186

7.1.1　通用机和图灵机停机问题 187

7.1.2　字等价问题的算法不可解 188

7.1.3　关于逻辑公式的可推导性问题 190

7.2　规范算法和算子算法 191

7.2.1　形式系统？波斯特产生式 191

7.2.2　规范算法 194

7.2.3　算子算法 195

7.3　多带机 200

7.3.1　一般多带机 200

7.3.2　明斯基（Minky）机 202

7.3.3　一致产生式系统 207

7.3.4　诺依曼自动机 211

7.4 刁番图方程 214

7.4.1　刁番图谓词和刁番图函数 215

7.4.2　算术表达式 218

7.4.3　自然数的多项式表示 221

7.4.4　指数方程 223

7.4.5　谓词u=v？是刁番图的 227

第八章　计算复杂性理论 228

8.1　计算复杂性测度 228

8.1.1　计算问题的表达函数 228

8.1.2　计算复杂性测度 229

8.1.3　计算复杂性与函数值之间的关系 230

8.1.4　加速定理 233

8.2　复杂性类 236

8.2.1　复杂性的限制 237

8.2.2　关于计算的模拟和并行的问题 241

8.2.3　复杂性类的命名 245

8.2.4　机器容量 248

8.3　计算复杂性分析 249

8.3.1　确定性计算和非确定性计算 250

8.3.2　关于相似性问题 251

8.3.3　P-语言类和NP-语言类 255

8.3.4　NP完全问题 258

8.4　相对化计算复杂性问题 262

8.4.1　相对化P与NP的建立 262

8.4.2　P=NP的相对化和P≠NP的相对化 264

8.4.3　依赖于信息源的NP格集 268

8.4.4　相对化指数时间复杂性问题 274

参考文献 276