《计算理论》求取 ⇩

第一章　关于数学基础问题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