計(jì)算理論解析

第1章計(jì)算的對象和本質(zhì)1
參考文獻(xiàn)6
第2章可計(jì)算函數(shù)——遞歸函數(shù)7
2.1分解計(jì)算、逐步計(jì)算的思想8
2.2原始函數(shù)10
2.3遞歸函數(shù)的構(gòu)造方法11
2.3.1復(fù)合方法12
2.3.2遞歸方法12
2.4遞歸函數(shù)的家族21
2.5遞歸函數(shù)的通俗解釋22
參考文獻(xiàn)23
第3章計(jì)算機(jī)的數(shù)學(xué)原理25
3.1數(shù)學(xué)運(yùn)算的基礎(chǔ)25
3.2希爾伯特第十個問題及其自動化解決思想28
3.3圖靈機(jī)原理32
3.4圖靈機(jī)的局部改進(jìn)和變形50
3.4.1多帶圖靈機(jī)50
3.4.2圖靈機(jī)的復(fù)合53
3.4.3圖靈機(jī)參數(shù)的限定57
參考文獻(xiàn)57
[1]計(jì)算理論解析[1]目錄〖2〗第4章語言的計(jì)算59
4.1圖靈計(jì)算的分類59
4.2語言的可計(jì)算性61
4.3作為枚舉器的圖靈機(jī)69
4.4作為語言識別器（接受器）的圖靈機(jī)70
4.5圖靈機(jī)和短語語法72
4.6線性有界自動機(jī)與上下文有關(guān)語法77
4.7下推自動機(jī)與上下文無關(guān)語法83
4.8確定型有窮自動機(jī)與正則語法86
4.9不確定型有窮自動機(jī)與正則語法89
4.10自動機(jī)接受的語言94
參考文獻(xiàn)95
第5章判定問題的可計(jì)算性97
5.1基本概念97
5.2不可判定性問題實(shí)例98
5.2.1丟番圖方程整數(shù)解問題99
5.2.2對角線函數(shù)102
5.2.3停機(jī)問題104
5.2.4邏輯蘊(yùn)涵106
5.2.5哥德爾語句G109
參考文獻(xiàn)110
第6章計(jì)算模型的應(yīng)用112
6.1計(jì)算機(jī)模擬圖靈機(jī)112
6.2語言識別和語法驗(yàn)證115
6.3邏輯推理123
6.4計(jì)算復(fù)雜性分析133
參考文獻(xiàn)139