本书是理论计算机科学的入门教材，主要介绍递归函数、算盘机、λ-演算、组合逻辑和Turing机等计算模型。书中每章附有适量习题，供读者选做。
本书可作为高等学校计算机及相关专业高年级本科生和研究生的教材，也可作为计算机科学与技术研究人员的参考书。
- 第一章递归函数
- 1.1 数论函数
- 1.2 配对函数
- 1.3 初等函数
- 1.4 原始递归函数
- 1.5 递归函数
- 1.6 结论
- 习题
- 第二章算盘机
- 2.1 算盘机的定义
- 2.2 算盘机可计算函数
- 2.3 算盘机的计算能力
- 习题
- 第三章λ-演算
- 3.1 λ-演算的语法
- 3.2 转换
- 3.3 归约
- 3.4 Church-Rosser 定理
- 3.5 不动点定理
- 3.6 递归函数的λ-可定义性
- 3.7 与递归论对应的结果
- 习题
- 第四章组合逻辑
- 4.1 组合子的形式系统
- 4.2 弱归约
- 4.3 CL 与λ的对应
- 习题
- 第五章Turing 机
- 5.1 Turing 机的形式描述
- 5.2 Turing 机的计算能力
- 5.3 可判定性与停机问题
- 5.4 通用Turing 机
- 5.5 Church-Turing 论题
- 习题
- 参考文献
