可計算性理論

前言
第一章可計算性理論基礎(chǔ)知識
1關(guān)于可計算性的基本概念
2算法可計算函數(shù)的定義：無窮存儲機器
3遞歸函數(shù)的可計算性
4對程序配數(shù),Smn定理,通用函數(shù)定理
5對角線方法
6遞歸定理
第二章可計算枚舉集
1可計算枚舉集的基本性質(zhì)
2不可解問題
3創(chuàng)造集,Post問題
4單純集
5超單純集
6對局方法,極大集,e-狀態(tài)方法
7用改進(jìn)的Post思想對Post問題的解
8能行禁集和可構(gòu)造禁集
9模引理和極限引理
第三章有窮和無窮延伸方法
1有窮延伸方法介紹
2力迫法介紹
3Kucera解決Post問題的方法
4余無窮的無窮延伸方法
5極小度
第四章有窮損害優(yōu)先方法
1引言
2有窮損害優(yōu)先方法介紹
第五章無窮損害優(yōu)先方法
1真步方法
2樹構(gòu)造方法
3彈球機方法
第六章有窮損害優(yōu)先方法補充
1非鉆石格的嵌入與分杈度
2同時區(qū)間允許
第七章計算復(fù)雜性理論
1抽象計算復(fù)雜性
2多項式計算復(fù)雜性
第八章及時單純集和間段.余間段方法
第九章n—可計算枚舉集和可計算逼近函數(shù)的圖靈度
1可計算枚舉差集(d.c.e.)
2n—可計算枚舉集的定義和基本性質(zhì)
3n—可計算枚舉度(n〉1)的結(jié)構(gòu)研究
4Dn(n〉1)中的可杯性定理
第十章樹構(gòu)造和O—方法
1樹構(gòu)造的基本思路
2定理和需求：Lachlan非囿界定理
3基本模塊
4構(gòu)造
5驗證
6相關(guān)結(jié)果和問題
第十一章囿界極小度定理
1介紹
2需求和基本模塊
3多個需求相結(jié)合時的基本模塊
4策略和優(yōu)先樹
5構(gòu)造
6驗證
參考文獻(xiàn)