計算理論解析

內容簡介

本書介紹計算模型理論，包括計算的對象、本質、定義、分類、表達、邏輯和機械實現方法，以及計算模型的典型套用。

全書共分為6章。第1章介紹計算的對象和本質，將離散變數作為圖靈計算（離散變數計算）的對象，將其邏輯確定性和機械能行可計算性作為圖靈計算的本質；第2章介紹可計算函式——遞歸函式；第3章介紹計算機的數學原理；第4章介紹語言的計算；第5章介紹判定問題的可計算性；第6章介紹計算模型的典型套用。

本書是計算理論（計算模型、形式語言與自動機）、計算機科學技術史、邏輯學、語言學、數學、哲學的交叉研究，也是通過淺顯易懂的講解方式進行計算機核心理論教學的嘗試。作者力圖為計算機相關人員提供一個計算的本質特徵的“靈魂”描述及其通俗解釋，以使得計算機軟硬體的所有任務、過程，特別是軟體的表達與執行歸結為數學原理和邏輯本質。

本書適合作為高等院校計算機、通信、自動化、軟體工程、信息管理、數理邏輯與數學基礎、生成轉換語言學等專業本科生和研究生的教材。同時，由於本書內容深入淺出，能夠被僅具有基本數學知識的人讀懂，因此也可供對計算機理論感興趣的廣大科技工作者參考。

圖書目錄

第1章計算的對象和本質1

參考文獻6

第2章可計算函式——遞歸函式7

2.1分解計算、逐步計算的思想8

2.2原始函式10

2.3遞歸函式的構造方法11

2.3.1複合方法12

2.3.2遞歸方法12

2.4遞歸函式的家族21

2.5遞歸函式的通俗解釋22

參考文獻23

第3章計算機的數學原理25

3.1數學運算的基礎25

3.2希爾伯特第十個問題及其自動化解決思想28

3.3圖靈機原理32

3.4圖靈機的局部改進和變形50

3.4.1多帶圖靈機50

3.4.2圖靈機的複合53

3.4.3圖靈機參數的限定57

參考文獻57

[1]計算理論解析[1]〖2〗第4章語言的計算59

4.1圖靈計算的分類59

4.2語言的可計算性61

4.3作為枚舉器的圖靈機69

4.4作為語言識別器（接受器）的圖靈機70

4.5圖靈機和短語語法72

4.6線性有界自動機與上下文有關語法77

4.7下推自動機與上下文無關語法83

4.8確定型有窮自動機與正則語法86

4.9不確定型有窮自動機與正則語法89

4.10自動機接受的語言94

參考文獻95

第5章判定問題的可計算性97

5.1基本概念97

5.2不可判定性問題實例98

5.2.1丟番圖方程整數解問題99

5.2.2對角線函式102

5.2.3停機問題104

5.2.4邏輯蘊涵106

計算理論解析

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條