目录

第一章 可计算函数

§1理想计算机

§2可计算函数的概念

§3程序的连接

§4生成可计算函数的方法

§5归纳集合

习题

第二章 原始递归函数

§1基本概念和基本定理

§2原始递归谓词

§3串值递归和二重递归

§4哥德尔β函数

§5配对函数

习题

第三章 部分 递归函数和一般递归函数

§1部分递归函数的概念

§2一般递归谓词

§3阿克曼函数

§4阿克曼函数的一般递归性

§5等式系

习题

第四章 理想机和等式系的算术化

§1理想机M的算术化

§2关于二进位数的几个原始递归函数

§3程序编码函数的原始递归性

§4范式定理和s-m-n定理

§5等式系的算术化

§6车赤论题

习题

第五章 不可解的判定问题

§1递归可枚举谓词

§2不可解的判定问题

习题

第六章 递归可枚举集合

§1递归集合和递归枚举集合的概念

§2递归可枚举集合的性质

§3创造集合和单纯集合

§4递归变换群的概念

习题

§1问题的转化

第七章 丢番图方程

§2丢番图谓词是递归枚举谓词

§3递归枚举谓词是拟丢番图谓词

§4正规序列

§5受囿全称量词运算保持谓词的丢番图性质

习题

第八章 相关递归性和克林尼分层

§1理想计算机MO

§2相关递归性

§3强归约性

§4非递归谓词的分类

§5非递归谓词的表示

习题

参考文献