这本生动、简洁的书基于作者在莫斯科大学力学数学系的本科生课程讲义，涵盖了计算的一般理论的基本概念。《可计算函数》从可计算函数的定义和一个算法开始，讨论了可判定性、可数性、通用函数、编号系统及其性质、m-完全性、不动点定理、算术分层、oracle计算、不可判定性的度。作者还介绍了一些特殊的函数模型，如Turing机和递归函数。
《可计算函数》可供数学和计算机专业的本科生阅读，也可供所有希望学习计算的一般理论的基础知识的数学家和程序员使用。
- 前辅文
- 第一章 可计算函数、可判定集与可数集
- 1 可计算函数
- 2 可判定集
- 3 可数集
- 4 可数集与可判定集
- 5 可数性与可计算性
- 第二章 通用函数与不可判定性
- 1 通用函数
- 2 对角构造
- 3 可数的不可判定集
- 4 可数的不可分集
- 5 单集:Post 构造
- 第三章 编号与运算
- 1 Gödel 通用函数
- 2 可计算函数的可计算序列
- 3 Gödel 通用集
- 第四章 Gödel 编号系统的性质
- 1 编号集
- 2 旧函数的新编号
- 3 Gödel 编号系统的同构
- 4 函数的可数性
- 第五章 不动点定理
- 1 不动点与等价关系
- 2 打印程序文本的程序
- 3 系统的技巧: 另一个证明
- 4 几点附注
- 第六章 m-可约性与可数集的性质
- 1 m-可约性
- 2 m-完全集
- 3 m-完全性与有效不可数性
- 4 m-完全集的同构
- 5 产生集
- 6 不可分集的对
- 第七章 Oracle 计算
- 1 Oracle 机
- 2 相对可计算性: 等价描述
- 3 相对化
- 4 {\bf 0 '-计算
- 5 不可比集
- 6 Friedberg-Muchnik 定理: 构造的一般方案
- 7 Friedberg-Muchnik 定理: 胜出条件
- 8 Friedberg-Muchnik 定理: 优先方法
- 第八章 算术分层
- 1 类\Sigma _n 和\Pi _n
- 2 \Sigma _n 和\Pi _n 中的通用集
- 3 跳跃运算
- 4 分层中集的分类
- 第九章 Turing 机
- 1 简单的可计算模型: 需要它们做什么?
- 2 Turing 机: 定义
- 3 Turing 机: 讨论
- 4 字问题
- 5 Turing 机的模拟
- 6 Thue 系统
- 7 半群、生成元和关系
- 第十章 可计算函数的算术化
- 1 有限个变量的程序
- 2 Turing 机和程序
- 3 可计算函数是可算术化的
- 4 Tarski 定理和Gödel定理
- 5 Tarski 定理和Gödel定理的直接证明
- 6 算术分层和量词交换数
- 第十一章 递归函数
- 1 原始递归函数
- 2 原始递归函数的例
- 3 原始递归集
- 4 递归的其他形式
- 5 Turing 机和原始递归函数
- 6 部分递归函数
- 7 Oracle 可计算性
- 8 生长率的估计、Ackermann 函数
- 参考文献
- 人名表
- 索引
