目录 1
序言 1
第一章 能行的 1
1.1 能行性定义 1
8.1 它们是什么 26 2
1.2 现代毕达哥拉斯 5
1.3 算法 8
1.4 Berry悖论 11
练习 15
附录 数学基础中的能行性 17
1.5 数学原理以及无穷带来的麻烦 18
1.6 构造数学 23
1.7 物理学中的能行过程 28
1.8 物理的算术化 30
1.9 几个类比 33
第二章 数学基础Ⅰ 34
2.1 引言 34
2.2 函数的意义及其扩充 35
2.3 被看作由一个集合映射到另一个集合的函数 37
2.4 定义函数关系的几种方法 39
2.5 定义在非自然数对象上的函数 41
2.6 函数的函数 42
2.7 关系 44
2.8 函数的标记和λ表示 45
2.9 定义集合的发生法 48
2.10 形式系统 49
2.11 算术化 53
2.12 布尔代数 55
2.13 命题演算的公理化表示法 63
2.14 反证法 64
2.15 建立已知真值表的布尔表达式 65
2.16 关于“波兰表示法” 66
练习 67
第三章 数学基础Ⅱ（应用） 71
3 1 布尔代数的实现 71
3.2 二进制算术与布尔代数的完善结合 75
3.3 集合的布尔代数 80
3.4 各种专门表示法及其使用 84
3.6 集合论在数学和计算中所起的作用 86
3.5 集合的乘积 86
3.7 超穷数理论 90
3.8 超穷数理论在计算上的应用 95
练习 97
附录 图论基础 100
3.9 图论的一些基本概念 100
3.10 计算中图结构的各种例子 105
3.11 计算机中的图的编码 108
3.12 一个与图有关的问题——最短路径问题——的算法解的例子 112
第四章 递归函数 116
4.2 “递归”定义 117
4.1 引言 117
4.3 基本递归函数 119
4.4 可使函数生成运算得以实现的程序设计语言的特点 122
4.5 原始递归函数类 123
4.6 Ackermann函数 125
4.7 部分递归函数类 129
4.8 关于这些基本运算同任何通用计算机或语言所必须提供的设施之间的关系 132
4.9 建立在生成部分递归函数基础之上的程序设计语言PR ECL 133
4.10 关于术语“递归”与“迭代”的注记 135
4.11 原始递归与数学归纳 138
4.12 用迭代代替极小化 140
4.13 关于集合：原始递归集合，递归集合，递归可列集合 142
4.14 关于结构程序设计 146
练习 150
第五章 图灵机和可计算性 154
5.1 图灵机的研究动机 154
5.2 图灵机的组织 157
5.3 用图灵机计算函数 159
5.4 一个图灵机的瞬间描述 161
5.5 输入和输出数据的表示法 162
5.6 附加约定 163
5.7 某些基本的数据处理操作 168
5.8 一些更复杂的机器操作 170
5.9 图灵机的算术化 173
5.10 “证明”若一函数是图灵机可计算的，则它是部分递归的 176
5.11 在计算的“现实”世界中的一些推论 178
练习 180
第六章 通用图灵机，可计算性理论的一些推论，图灵机的变种 183
6.1 通用图灵机 185
6.2 停止问题 186
6.3 判定问题 189
6.4 停止问题的变种 190
6.5 一个不可计算的函数 193
6.6 一个不递归的递归可列集 195
6.7 图灵机是能行可列的 196
6.8 忙碌的海狸问题 197
6.9 图灵机的变种，有多于一个带子或有高维带子的机器 199
6.10 非确定性图灵机 200
6.11 王氏机器 203
6.12 She pherdson-Sturgis的寄存器机器 204
6.13 细胞状自动机 207
6.14 图灵机用作符号操作系统 209
6.15 “正规”重写规则的使用和某些特殊的符号操作系统 211
6.16 “捉人”游戏问题 214
6.17 可计算的数 216
6.18 哥德尔的结果的提示 219
6.19 关于不完备性结果以及人是否机器问题的一些可能推断的讨论 221
练习 222
第七章 关于自动机的一般评论 225
7.1 什么是自动机 226
7.2 “状态”和“机制”的概念 228
7.3 自动机的分类 231
7.4 自动机完成的功能 233
7.5 自动机的幅度 234
7.6 有下推存储的机器与有栈的机器 236
7.7 计算中的非确定性与蒙特卡罗方法 238
7.8 自动机的构造块 241
7.9 通用逻辑元素 246
7.10 反馈和记忆 250
7.11 判断器 253
7.12 自动机与思想——图灵测试 255
练习 258
第八章 有穷自动机 261
8.2 怎样描述它们 263
8.3 顺序机器 265
8.4 有穷自动机作为识别设备 267
8.5 翻译机能计算什么样的函数 270
8.6 非确定性的有穷自动机 274
8.7 在讨论有穷自动机时有用的各种概念 275
8.8 构造一个等价于一个给定NDFA的确定性有穷自动机 277
8.9 任一正规集总能由某有穷自动机识别 280
8.10 正规表达式，正规集的一个表示法 281
8.11 有穷自动机的最小化 282
8.12 能够反向地读带子的有穷自动机 284
8.13 树自动机 287
练习 289
第九章 形式语言——导论 294
9.1 自然语言与形式语言 295
9.2 符号处理系统——重写规则 298
9.3 这些系统的形式化 302
9.4 语言的分类 306
9.5 由文法定义的语言的例子 309
9.6 语法、语义和二义性 314
9.7 分析 319
9.8 有穷自动机在识别和分析上下文无关语言的句子中的某些应用 324
9.9 在分析中前缀的识别 329
9.10 一个具有足够长的句子的语言是上下文无关的必要条件 332
练习 335
第十章 形式语言——与自动机和程序设计语言的进一步关系 338
10.1 Chomsky体系中用自动机类给出的语言的定义 340
10.2 某些在分析程序设计语言的句子或程序中特别重要的有限制的上下文无关文法 343
10.3 ALGOL不是上下文无关的 347
10.4 POST的对应问题 348
10.5 关系的传递闭包 354
10.6 应用关系传递闭包于形式语言的一个问题 357
10.7 关于程序正确性证明 359
10.8 语义的定义 364
10.9 维也纳定义语言 365
10.10 LINCOS，一个用于宇宙交往的语言 368
练习 376
第十一章 计算复杂性的研究 380
11.1 复杂性与简单性 381
11.2 关于增长率的数学描述 383
11.3 信息的数学量度 385
11.4 有穷序列的信息容量 387
11.5 机器的复杂性 388
11.6 复杂性理论中的各类问题 390
11.7 公理化的、独立于机器的部分可计算函数复杂性的定义方法 396
11.8 加速定理 398
11.9 可由有穷自动机计算的函数 399
11.10 可预测的复杂性——初等算术函数的Ritchie分级结构 401
11.11 电路中“扇入”元件的使用及Winograd的关于加法和乘法的最小界限 403
11.12 时间与空间的交易 408
11.13 概率算法 410
11.14 “实时”计算 413
11.15 关于有穷序列的随机性 416
11.16 一个尚未解决的问题，？＝？吗？ 417
练习 418
第十二章 总结数学思想对计算的影响——剖析与评述 421
12.1 基本概念及有关几个重要历史发展阶段的扼要评述 421
12.2 皮亚诺公理 423
12.3 可计算性 424
12.4 现代数学的特征——抽象化和公理化 425
12.5 计算对数学产生的影响 428
12.6 四色定理 429
12.7 有关的主要数学概念一览 434
12.8 一般性评述，大事记 435
附录 现代代数的影响 437
12.9 计算机科学与代数 437
12.10 机器的范畴 441
参考文献 444
索引 453