本書介紹計算模型理論，包括計算的對象、本質、定義、分類、表達、邏輯和機械實現方法，以及計算模型的典型應用。
全書共分為6章。第1章介紹計算的對象和本質，將離散變量作為圖靈計算（離散變量計算）的對象，將其邏輯確定性和機械能行可計算性作為圖靈計算的本質；第2章介紹可計算函數——遞歸函數；第3章介紹計算機的數學原理；第4章介紹語言的計算；第5章介紹判定問題的可計算性；第6章介紹計算模型的典型應用。
本書是計算理論（計算模型、形式語言與自動機）、計算機科學技術史、邏輯學、語言學、數學、哲學的交叉研究，也是通過淺顯易懂的講解方式進行計算機核心理論教學的嘗試。作者力圖為計算機相關人員提供一個計算的本質特征的“靈魂”描述及其通俗解釋，以使得計算機軟硬件的所有任務、過程，特別是軟件的表達與執行歸結為數學原理和邏輯本質。
本書適合作為高等院校計算機、通信、自動化、軟件工程、信息管理、數理邏輯與數學基礎、生成轉換語言學等專業本科生和研究生的教材。同時，由于本書內容深入淺出，能夠被僅具有基本數學知識的人讀懂，因此也可供對計算機理論感興趣的廣大科技工作者參考。
1、深入探討圖靈可計算性的數學原理，將圖靈計算模型具體、詳盡、直觀地解釋為遞歸函數，從而使讀者徹悟作為一個物理過程的圖靈計算其數學“靈魂”------離散計算的核心思想和原理----是什么。
2、對圖靈計算模型的數學函數-----遞歸函數進行了綜述和分類，使得讀者能夠從歷史和邏輯的視野洞悉遞歸函數的發展脈絡和形式結構及其邏輯分類。
3、以深入淺出的方式講解和評介計算的基本原理和方法，用了較多的圖示，直觀易懂；關鍵問題提供了作者自己編纂的例題，形象而淺顯。
4、將跨學科的分割的一體化內容進行了融匯貫通，主要地將計算的數學哲學、數理邏輯、計算與符號推導的形式語言學（喬姆斯基文法）融入了計算理論，使讀者能夠全方位了解知識的整體性和不同側面。
本書講解計算的主要理論和方法，期望為讀者解析如下內容:
（1） 什么是計算？如何概括并形式化地表示計算?
（2） 計算的種類有哪些？它們的核心特征是什么?
（3） 如果符號是被計算的對象和結果，那么，作為符號的語言是可以被計算出來的嗎?
（4） 如何通過計算判定一個問題的答案的對錯?
（5） 計算模型——作為對計算本質的描述和抽象——的典型應用（模型的實例化）是什么?
大致上說，本書內容相當于“計算模型”“形式語言與自動機理論”“計算與語言”的課程內容，是這些課程的基礎、核心知識及其原理、方法和效果的形象和通俗的解釋。
作者認為，當前“計算模型”“形式語言與自動機理論”“計算與語言”等課程的教學存在一些問題，這些問題集中在以下兩個方面。
（1） 對于計算模型，語言學和計算機科學割裂了同一或密切相關的知識。在語言學領域，喬姆斯基語法是被廣為接受的，但是這些語言學的研究很少介紹這些語法與計算機的本質、圖靈機的運行之間的關系；同樣，一個計算機專業的人可以知曉自動機的類型，卻缺少對喬姆斯基語法的特征和分析方法的了解。這種學科分割的狀況可以解釋我國語言學和計算機科學技術學科發展的一些問題。語言學界承認，近百年來在語言學核心理論、有重要影響力的理論和方法方面，我國貢獻很少。我們缺少像索緒爾、喬姆斯基、蒙太古等人的語言學理論那樣的開創性成果，而實際上這些語言成果的原理都是在描述可計算性，通俗地說是“計算”相關的或計算本質的語言學描述。同樣，在計算機科學技術領域，一個程序員會為自己熟練運用一門語言如Java而自豪，但是其中很多人對Java語法的表示卻知曉不多，甚至不知道喬姆斯基語法為何物。我國的計算機應用似乎走在了世界的前列，但這些基本上是計算機某種語言的應用，卻很少研制出一門計算機編程語言——那么多層出不窮的計算機編程語言: C，C++,Python,Prolog,Mathematica等都是計算理論的原創國家研制的，它的底層除了那些技術手段以外，其靈魂基本上是邏輯及可計算語言學的原理。一個學習語言學的人可能會對計算機程序員感到很陌生，而后者可能感覺前者是個文科領域的異類，但是計算機界的人士似乎并不思考為什么只能應用別人研制的編程語言，自己卻不能研制一門語言。
[1]計算理論解析[1]前言〖2〗（2） 對于圖靈機本質的介紹不夠深入。計算模型（圖靈計算、形式理論與自動機等）課程基本上只有部分碩士研究生才會去學習，那么多計算機科學技術的本科生直到畢業也不知道圖靈計算為何物——自己學的做的、自己的“飯碗”，甚至思維都是圖靈計算，但就是不知道什么是“圖靈計算”！這樣的程序員就像一個泥瓦匠，樓房蓋完了也不知如何設計房屋，完全處于工匠地位。這種狀況的根源是在專業教學中缺乏對圖靈機原理的充分介紹和講解。
雖然不敢說本書能在多大程度上解決上述問題，但還是力圖在架設計算機科學技術與其他學科的橋梁方面有所禆益。
概言之，計算理論、計算模型課程，重要的不僅是介紹一些個別技術，還應該被當作計算的核心構架而被提綱挈領，應該作為計算的靈魂而被透徹理解，應該是科學史中的人類計算思想發展的脈絡而被哲學家導引并被看穿。
本書力圖體現出如下特點。
（1） 注重知識的系統性。深入全面介紹概念的背景、本意、關聯關系，將知識放置在數學、邏輯學、計算機科學技術、語言學、科學技術史的背景下統一介紹，力圖克服知識因不同學科劃分而被割裂的常見弊端。
例如，對遞歸函數的介紹，從遞歸函數的源頭——斯克倫、希爾伯特的定義開始介紹，將邏輯、數學、數學史、計算哲學統一起來，有助于讓讀者理解計算的“靈魂”，能夠使千變萬化的計算有一個根本的概念和歷史的淵源圖景，這是在類似課程的教科書里不多見的。
（2） 側重介紹圖靈機是如何表示和實現遞歸運算的，詳細地說明了圖靈計算的本質是遞歸計算，將圖靈機表述為遞歸函數，圖示了計算機對圖靈機的模擬模式。這些內容側重圖靈機的“靈魂”，即圖靈機實現遞歸函數的邏輯表示。
（3） 提出自己的獨立觀點，不只是介紹知識內容和進展。
例如，本書對于遞歸函數的分類，提出了一個遞歸函數分類表，在遞歸函數的概念內涵解釋上，對我國學術界將“一般遞歸函數”解釋為μ全遞歸函數，即將一般遞歸函數解釋為μ部分遞歸函數的子類的觀點提出了不同意見。本書認為“一般遞歸函數”就是廣義遞歸函數，它是遞歸函數的最廣義的遞歸函數類。
再如，本書在計算分類上提出了圖靈計算包括枚舉、語言識別、函數判定三類，并給出其各自的屬性特征。
（4） 突出重點，側重介紹知識主干，舍棄一些衍生的、枝節的知識。
（5） 力圖深入淺出，特別注意用圖示直觀展示內容。
（6） 附有較多例題，便于理解和實踐相關問題和方法。這些例題絕大多數是作者自己編纂、提出和設計的。
盡管如此，本書仍難免存在疏漏和不足，歡迎讀者指正!
作者張寅生
2016年1月
第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
5.2.5哥德爾語句G109
參考文獻110
第6章計算模型的應用112
6.1計算機模擬圖靈機112
6.2語言識別和語法驗證115
6.3邏輯推理123
6.4計算復雜性分析133
參考文獻139
新書資訊