可計算性理論

前言
第一章可計算性理論基礎知識
1關于可計算性的基本概念
2算法可計算函數的定義：無窮存儲機器
3遞歸函數的可計算性
4對程序配數,Smn定理,通用函數定理
5對角線方法
6遞歸定理
第二章可計算枚舉集
1可計算枚舉集的基本性質
2不可解問題
3創(chuàng)造集,Post問題
4單純集
5超單純集
6對局方法,極大集,e-狀態(tài)方法
7用改進的Post思想對Post問題的解
8能行禁集和可構造禁集
9模引理和極限引理
第三章有窮和無窮延伸方法
1有窮延伸方法介紹
2力迫法介紹
3Kucera解決Post問題的方法
4余無窮的無窮延伸方法
5極小度
第四章有窮損害優(yōu)先方法
1引言
2有窮損害優(yōu)先方法介紹
第五章無窮損害優(yōu)先方法
1真步方法
2樹構造方法
3彈球機方法
第六章有窮損害優(yōu)先方法補充
1非鉆石格的嵌入與分杈度
2同時區(qū)間允許
第七章計算復雜性理論
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策略和優(yōu)先樹
5構造
6驗證
參考文獻