《计算机科学理论 程序设计途径》

第一章　概述1

1.1 引言1

1.2　第一部分：元计算机科学4

目录5

序言5

1.3　第二部分：关于计算机科学理论11

第一部分　元计算机科学22

第二章　抽象机方法22

2.1 引言22

2.2　基本机和有限状态时序机23

2.3　输入序列；状态28

2.4　FSM的局限性34

2.5 图灵机36

2.6　通用图灵机47

2.7　shannon对TM复杂性的度量50

2.8　其他类似计算机的抽象机56

第三章　计算机科学的局限性63

3.1 引言63

3.2　不可计算的函数66

3.3　可枚举性与可判定性70

3.4　不可解性成果概述86

第四章　函数或程序设计式方法116

4.1 引言116

4.2　一般递归函数121

4.3　Ackermann函数以及对复杂性的再考察137

5.2　图灵机的一个GRF模拟程序147

5.1 引言147

第五章　支持图灵论题的证据147

5.3　GRF的TM编译程序157

5.4　作为数据结构的数162

第二部分　关于计算机科学理论168

第六章　McCarthy的开拓性研究168

6.1　引言168

6.2　McCarthy的形式系统170

6.3　S-表达式181

6.4　形式系统的应用——程序等价性190

6.5　形式系统的应用——程序设计语言的语义206

第七章　程序的可靠性215

7.1　引言215

7.2　程序测试220

7.3　证明程序正确性的归纳断言技术230

7.4　Zohar Manna的基础研究256

7.5　述评264

第八章　语义问题269

8.1　引言269

8.2　λ-演算276

8.3　操作语义：强调机器的作用285

8.4　数学语义：不强调机器的作用298

附录A 数学预备知识312

附录B 程序设计说明332

参考文献337

著者索引346

汉英名词索引348