可計算性與計算複雜性導引

內容簡介

此書讓你看清這個社會人心本質，思索宇宙人生，感悟生命的原動力，改變自我絕對一本啟蒙好書。

一直跟著此書作者討論，非常受益，值得認真看看，認真思考。此書雖然用的辭藻不華麗，但正因為這樣樸實的語句，更能為大眾所理解，所接受，作者將一部深奧難懂的精神分析學、社會關係學、等等，匯集到此書當中，用最親切的語言，最易於大眾理解的語言，一語道破天機。

全書理論體系相對完整，採用了儘可能多的實際操作案例來解釋和闡述相應的具體套用。

圖書目錄

第一章程式設計語言和可計算函式

1.1 預備知識

1.2 church-turing論題

1.3 程式設計語言

1.4 可計算函式

1.5 宏指令

習題

第二章原始遞歸函式

2.1 原始遞歸函式

2.2 原始遞歸謂詞

2.3 疊代運算、有界量詞和極小化

2.4 配對函式和godel數

2.5 原始遞歸運算

2.6 ackermann函式

2.7 字函式的可計算性

習題

第三章通用程式

3.1 程式的代碼

3.2 停機問題

3.3 通用程式

3.4 遞歸可枚舉集

習題

第四章 turing機

4.1 turing機的基本模型

4.2 turing機的各種形式

4.3 turing機與可計算性

4.4 turing機接受的語言

4.5 非確定型turing機

習題

第五章過程與文法

5.1 半thue過程

5.2 用半thue過程模擬turing機

5.3 文法

5.4 再論遞歸可枚舉集

5.5 部分遞歸函式

5.6 再論church-turing論題

習題

第六章不可判定的問題

6.1 判定問題

6.2 turing機的停機問題

6.3 字問題和post對應問題

6.4 有關文法的不可判定問題

6.5 一階邏輯中的判定問題

習題

第七章正則語言

7.1 chomsky譜系

7.2 有窮自動機

7.3 有窮自動機與正則文法的等價性

7.4 正則表達式

7.5 非正則語言

習題

第八章上下文無關語言

8.1 上下文無關文法

8.2 chomsky範式

8.3 bar-hillel泵引理

8.4 下推自動機

8.5 上下文無關文法與下推自動機的等價性

8.6 確定型下推自動機

可計算性與計算複雜性導引

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條