《可计算性引论》求取 ⇩

第一章抽象算法族与算法族可计算性2

§1.1函数与算法2

1.1.1函数2

目录2

1.1.2算法及其分类5

1.1.3抽象算法族7

练习1.110

§1.2抽象算法族的基本性质12

1.2.1基础函数性质（BFP）12

1.2.2复合函数性质（CFP）12

1.2.3通用函数性质（UFP）14

1.2.4判定函数性质（DFP）17

1.2.5标号函数性质（IFP）20

练习1.223

1.3.1标准算法族26

1.3.2标准算法族的固有局限性26

§1.3标准算法族可计算性26

1.3.3标准算法族的计算能力30

练习1.336

第二章 程序算法族及其可计算性39

§2.1程序语言？39

练习2.144

§2.2 ？语言程序算法族可计算性45

2.2.1程序算法族可计算性的形式描述45

2.2.2初等函数与初等谓词是？程序可计算的48

2.2.3配对函数及程序编码57

2.2.4通用程序与标号计算程序63

练习2.271

第三章Turing机与Turing可计算性73

§3.1什么是Turing机73

3.1.1基本Turing机73

3.1.2基本Turing机实例80

3.1.3 Turing机的复合87

练习3.189

§3.2其他种类的Turing机91

3.2.1多道机以及其他的Turing机推广形式92

3.2.2单边机以及其他的Turing机限制形式95

练习3.299

§3.3通用Turing机100

3.3.1机和带的描述101

3.3.2通用机的构成104

练习3.3107

3.4.1 Turing机及其可计算性的形式描述108

§3.4 Turing机族及其可计算性108

3.4.2 Turing机标号112

3.4.3 Turing机族114

3.4.4计算通用函数的Turing机116

3.4.5计算标号函数的Turing机118

练习3.4119

§3.5Turing机族的计算功能及局限性120

3.5.1停机函数120

3.5.2标号计算函数122

3.5.3全性函数和等价性函数123

3.5.4递归定理125

练习3.5126

第四章原始递归函数129

§4.1初等函数集的不足129

练习4.1131

§4.2原始递归函数集132

4.2.1原始递归式132

4.2.2原始递归函数集135

练习4.2138

§4.3可以化为原始递归式的其他递归式140

4.3.1联立递归式140

4.3.2串值递归式143

练习4.3146

§4.4原始递归谓词148

§4.5 Loop程序与原始递归函数149

练习4.5155

§5.1 Ackerman函数156

5.1.1 Ackerman函数及基本性质156

第五章递归函数156

5.1.2 Ackerman函数的非原始递归性159

练习5.1163

§5.2μ-递归函数164

5.2.1μ-递归函数及其可计算性165

5.2.2 Ackerman函数的μ-递归性167

5.2.3 Turing可计算函数的μ-递归性173

练习5.2177

5.3.1一般递归式及递归函数集179

§5.3递归函数集179

5.3.2递归函数的可计算性181

5.3.3μ-递归函数的递归性182

练习5.3186

§5.4 Church-Turing论题186

5.4.1 Church-Turing论题186

5.4.2递归函数集是最小的标准算法族188

可计算函数集188

练习5.4191

第六章字函数及其可计算性193

§6.1∑*与∑*上的字函数193

6.1.1∑*上的原始递归字函数194

6.1.2∑*上的μ-递归字函数（递归字函数）198

练习6.1201

§6.2无零K进制与字的数表示201

6.2.1无零k进制与K进制的换算是203

原始递归可计算的203

6.2.2几个重要字函数的数论函数表示形式204

练习6.2206

§6.3∑*上字函数的可计算性讨论206

6.3.1程序语言？n206

6.3.2∑*上递归字函数的可计算性213

练习6.3213

第七章形式语言与自动机214

§7.1形式语言的生成与识别214

7.1.1形式语言的生成214

7.1.2形式语言的识别217

练习7.1219

§7.2正规语言和有穷自动机219

7.2.1 正规文法与正规语言219

7.2.2有穷自动机224

7.2.3有穷自动机与正规语言226

练习7.2232

§7.3正规语言的性质及正规表达式233

7.3.1正规语言的封闭特性233

7.3.2正规表达式238

7.3.3 Pumping引理及其应用241

练习7.3243

§7.4 上下文无关语言244

7.4.1上下文无关文法及上下文无关语言244

7.4.2文法树和导出树246

7.4.3 Chomsky标准形、Pumping引理及249

其他特性249

练习7.4254

§7.5下推自动机255

练习7.5259

§7.6形式语言的Chomsky分层259

7.6.1上下文有关语言259

7.6.2递归枚举语言263

7.6.3 Chomsky分层266

练习7.6267

第八章递归集、递归枚举集和判定问题268

§8.1递归集和递归枚举集268

8.1.1递归集和递归枚举集269

8.1.2递归关系和递归枚举关系279

练习8.1288

§8.2判定问题289

8.2.1判定问题求解的常用定理及方法292

8.2.2 Post对应问题297

8.2.3形式语言中的判定问题303

8.2.4其他判定问题简介307

练习8.2314

参考文献316