第一章抽象算法族与算法族可计算性 2
§1.1函数与算法 2
1.1.1函数 2
目录 2
1.1.2算法及其分类 5
1.1.3抽象算法族 7
练习1.1 10
§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.2 23
1.3.1标准算法族 26
1.3.2标准算法族的固有局限性 26
§1.3标准算法族可计算性 26
1.3.3标准算法族的计算能力 30
练习1.3 36
第二章 程序算法族及其可计算性 39
§2.1程序语言？ 39
练习2.1 44
§2.2 ？语言程序算法族可计算性 45
2.2.1程序算法族可计算性的形式描述 45
2.2.2初等函数与初等谓词是？程序可计算的 48
2.2.3配对函数及程序编码 57
2.2.4通用程序与标号计算程序 63
练习2.2 71
第三章Turing机与Turing可计算性 73
§3.1什么是Turing机 73
3.1.1基本Turing机 73
3.1.2基本Turing机实例 80
3.1.3 Turing机的复合 87
练习3.1 89
§3.2其他种类的Turing机 91
3.2.1多道机以及其他的Turing机推广形式 92
3.2.2单边机以及其他的Turing机限制形式 95
练习3.2 99
§3.3通用Turing机 100
3.3.1机和带的描述 101
3.3.2通用机的构成 104
练习3.3 107
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.4 119
§3.5Turing机族的计算功能及局限性 120
3.5.1停机函数 120
3.5.2标号计算函数 122
3.5.3全性函数和等价性函数 123
3.5.4递归定理 125
练习3.5 126
第四章原始递归函数 129
§4.1初等函数集的不足 129
练习4.1 131
§4.2原始递归函数集 132
4.2.1原始递归式 132
4.2.2原始递归函数集 135
练习4.2 138
§4.3可以化为原始递归式的其他递归式 140
4.3.1联立递归式 140
4.3.2串值递归式 143
练习4.3 146
§4.4原始递归谓词 148
§4.5 Loop程序与原始递归函数 149
练习4.5 155
§5.1 Ackerman函数 156
5.1.1 Ackerman函数及基本性质 156
第五章递归函数 156
5.1.2 Ackerman函数的非原始递归性 159
练习5.1 163
§5.2μ-递归函数 164
5.2.1μ-递归函数及其可计算性 165
5.2.2 Ackerman函数的μ-递归性 167
5.2.3 Turing可计算函数的μ-递归性 173
练习5.2 177
5.3.1一般递归式及递归函数集 179
§5.3递归函数集 179
5.3.2递归函数的可计算性 181
5.3.3μ-递归函数的递归性 182
练习5.3 186
§5.4 Church-Turing论题 186
5.4.1 Church-Turing论题 186
5.4.2递归函数集是最小的标准算法族 188
可计算函数集 188
练习5.4 191
第六章字函数及其可计算性 193
§6.1∑*与∑*上的字函数 193
6.1.1∑*上的原始递归字函数 194
6.1.2∑*上的μ-递归字函数（递归字函数） 198
练习6.1 201
§6.2无零K进制与字的数表示 201
6.2.1无零k进制与K进制的换算是 203
原始递归可计算的 203
6.2.2几个重要字函数的数论函数表示形式 204
练习6.2 206
§6.3∑*上字函数的可计算性讨论 206
6.3.1程序语言？n 206
6.3.2∑*上递归字函数的可计算性 213
练习6.3 213
第七章形式语言与自动机 214
§7.1形式语言的生成与识别 214
7.1.1形式语言的生成 214
7.1.2形式语言的识别 217
练习7.1 219
§7.2正规语言和有穷自动机 219
7.2.1 正规文法与正规语言 219
7.2.2有穷自动机 224
7.2.3有穷自动机与正规语言 226
练习7.2 232
§7.3正规语言的性质及正规表达式 233
7.3.1正规语言的封闭特性 233
7.3.2正规表达式 238
7.3.3 Pumping引理及其应用 241
练习7.3 243
§7.4 上下文无关语言 244
7.4.1上下文无关文法及上下文无关语言 244
7.4.2文法树和导出树 246
7.4.3 Chomsky标准形、Pumping引理及 249
其他特性 249
练习7.4 254
§7.5下推自动机 255
练习7.5 259
§7.6形式语言的Chomsky分层 259
7.6.1上下文有关语言 259
7.6.2递归枚举语言 263
7.6.3 Chomsky分层 266
练习7.6 267
第八章递归集、递归枚举集和判定问题 268
§8.1递归集和递归枚举集 268
8.1.1递归集和递归枚举集 269
8.1.2递归关系和递归枚举关系 279
练习8.1 288
§8.2判定问题 289
8.2.1判定问题求解的常用定理及方法 292
8.2.2 Post对应问题 297
8.2.3形式语言中的判定问题 303
8.2.4其他判定问题简介 307
练习8.2 314
参考文献 316