可計(jì)算性理論

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