計算機模型導引（簡體書）

《計算機科學與技術研究生系列教材：計算模型導引》是理論計算機科學的入門教材，主要介紹遞歸函數、算盤機、演算、組合邏輯和Turing機等計算模型。書中每章附有適量習題，供讀者選做。
《計算機科學與技術研究生系列教材：計算模型導引》可作為高等學校計算機及相關專業高年級本科生和研究生的教材，也可作為計算機科學與技術研究人員的參考書。．

宋方敏，南京大學計算機科學與技術系教授，博士生導師。
主要研究領域是數理邏輯和量子計算，曾主持國家自然科學基金項目、863項目和中法合作項目的研究，在國內外核心刊物上發表論文50余篇。曾獲國家教委科技進步三等獎、江蘇省優秀科技工作者稱號和2004年度教育部提名國家科學技術獎。為本科生主講“離散數學”和“數理邏輯”課程，為研究生主講“計算理論”課程。

《計算機科學與技術研究生系列教材:計算模型導引》可作為高等學校計算機及相關專業高年級本科生和研究生的教材，也可作為計算機科學與技術研究人員的參考書。

第一章遞歸函數
§1.1數論函數
§1.2配對函數
§1.3初等函數
§1.4原始遞歸函數
§1.5遞歸函數
§1.6結論
習題

第二章算盤機
§2.1算盤機的定義
§2.2算盤機可計算函數
§2.3算盤機的計算能力
習題

第三章γ演算
§3.1γ-演算的語法
§3.2轉換
§3.3歸約
§3.4Church-Rosser定理
§3.5不動點定理
§3.6遞歸函數的γ-可定義性
§3.7與遞歸論對應的結果
習題

第四章組合邏輯
§4.1組合子的形式系統
§4.2弱歸約
§4.3CL與氳畝雜
習題

第五章Turing機
§5.1Turing機的形式描述
§5.2Turing機的計算能力
§5.3可判定性與停機問題
§5.4通用Turing機
§5.5Church-Turing論題
習題
參考文獻．

在18世紀初，現代數學取得了輝煌的成果。G.W.Leibniz（1646—1716）是當時的杰出者，他是微積分學的創始人之一。作為數學家和哲學家，他為推動數理邏輯的發展也作出過重大的貢獻。Leibniz曾有一個宏偉的理想：
1.建立一種通用語言，使得所有的問題能在其中表述；
2.找出一種判定方法，解答所有在通用語言中表述的問題。
人們為實現這一理想付出了很多努力，直至20世紀才出現一些重要成果。謂詞邏輯和集合論的建立實際上完成了Leibniz的第一個理想，這歸功于一些一流的數學家，如Frege，Cantor，Russell，Hilbert和Godel.Leibniz的第二個理想成為了一個哲學問題：“是否存在一種通用的判定方法求解所有用通用語言表述的問題呢？”這就是所謂的Entscheidungsproblem①。
在1936年，Church和Turing獨立地給出了這個問題的否定答案。為了解決此問題，他們以不同的方式形式化定義了“可判定”的概念（或者“可計算”的概念）。事實上，他們給出了兩種不同的計算模型：Turing發明了一組機器——“Turing機”，并以此定義可計算性【Tur36】；Church發明了一個形式系統——“λ—演算”，并以此定義了可計算性【Chu32】。就這樣，λ—演算問世了。
當初建立λ—演算以及相關的組合邏輯旨在發展一個一般的函數理論，從而刻畫由函數或算子組合成其他算子的最基本的內容，以及擴展此理論使它具有邏輯概念，從而為邏輯甚至數學提供基礎。事實上，λ—演算的確是“函數的理論”，它的語法說明了函數是怎樣被構造的；而它的形式系統提供了函數相等性、函數定義和函數作用的公理化。然而，λ—演算不能勝任為數學提供基礎。Kleene和Rosser在1935年曾證明了Church原來的系統是不相容的；Curry曾給出了一個相容的組合邏輯系統，但太弱而不足以成為數學的基礎；Church在1941年給出了一個相容的系統，但其僅能處理函數；后來Curry及其學生在這方面做了很多工作，比如擴張純組合邏輯。
λ—演算與遞歸論密切相關。Church利用λ—可定義性形式化“能行可計算”的概念；Kleene證明了λ—可定義性等價于Godel的遞歸性【Kle36】；Turing證明了λ—可定義性等價于Turing可計算性【Tur37】；遞歸論中的一些定理（如s—m—n定理）的發現也受到λ—演算的啟示。