可计算性理论

　　本书全面系统地介绍了50年代至今在可计算性理论方面的主要方法与成果．主要内容包括：可计算性理论基础知识，可计算枚举集，有穷和无穷延伸方法，有穷损害优先方法，无穷损害优先方法，计算复杂性理论，及时单纯集和间段、余间段方法，n—可计算枚举集和可计算逼近函数的图灵度，树构造和O方法，囿界极小度定理．本书可供大学数学系和计算机科学系的教师和研究生、科研人员阅读．

暂缺《可计算性理论》作者简介

前言
第一章可计算性理论基础知识
1关于可计算性的基本概念
2算法可计算函数的定义：无穷存储机器
3递归函数的可计算性
4对程序配数,Smn定理,通用函数定理
5对角线方法
6递归定理
第二章可计算枚举集
1可计算枚举集的基本性质
2不可解问题
3创造集,Post问题
4单纯集
5超单纯集
6对局方法,极大集,e-状态方法
7用改进的Post思想对Post问题的解
8能行禁集和可构造禁集
9模引理和极限引理
第三章有穷和无穷延伸方法
1有穷延伸方法介绍
2力迫法介绍
3Kucera解决Post问题的方法
4余无穷的无穷延伸方法
5极小度
第四章有穷损害优先方法
1引言
2有穷损害优先方法介绍
第五章无穷损害优先方法
1真步方法
2树构造方法
3弹球机方法
第六章有穷损害优先方法补充
1非钻石格的嵌入与分杈度
2同时区间允许
第七章计算复杂性理论
1抽象计算复杂性
2多项式计算复杂性
第八章及时单纯集和间段.余间段方法
第九章n—可计算枚举集和可计算逼近函数的图灵度
1可计算枚举差集(d.c.e.)
2n—可计算枚举集的定义和基本性质
3n—可计算枚举度(n〉1)的结构研究
4Dn(n〉1)中的可杯性定理
第十章树构造和O—方法
1树构造的基本思路
2定理和需求：Lachlan非囿界定理
3基本模块
4构造
5验证
6相关结果和问题
第十一章囿界极小度定理
1介绍
2需求和基本模块
3多个需求相结合时的基本模块
4策略和优先树
5构造
6验证
参考文献