計算理論解析

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