本書主要介紹了計算模型領域的主要概念，方法和技術，旨在通過介紹遞歸函數(shù)，Lambda演算和Turing機來理解計算理論。本課程講述如下專題：遞歸函數(shù)、算盤機、Lambda演算、Turing機和Church論題。計算理論是計算機科學的理論基礎。
宋方敏，南京大學計算機科學與技術系教授，博士生導師。主要研究領域是數(shù)理邏輯和量子計算，曾主持國家自然科學基金項目、863項目和中法合作項目的研究，在國內(nèi)外核心刊物上發(fā)表論文50余篇。曾獲國家教委科技進步三等獎、江蘇省優(yōu)秀科技工作者稱號和2004年度教育部提名國家科學技術獎。為本科生主講“離散數(shù)學”和“數(shù)理邏輯”課程，為研究生主講“計算理論”課程。
第一章 遞歸函數(shù)
§1.1 數(shù)論函數(shù)
§1.2 配對函數(shù)
§1.3 初等函數(shù)
§1.4 原始遞歸函數(shù)
§1.5 遞歸函數(shù)
§1.6 結論
習題
第二章 算盤機
§2.1 算盤機的定義
§2.2 算盤機可計算函數(shù)
§2.3 算盤機的計算能力
習題
第三章 γ演算
§3.1 γ-演算的語法
§3.2 轉(zhuǎn)換
§3.3 歸約
§3.4 Church-Rosser定理
§3.5 不動點定理
§3.6 遞歸函數(shù)的γ-可定義性
§3.7 與遞歸論對應的結果
習題
第四章 組合邏輯
§4.1 組合子的形式系統(tǒng)
§4.2 弱歸約
§4.3 CL與氳畝雜
習題
第五章 Turing機
§5.1 Turing機的形式描述
§5.2 Turing機的計算能力
§5.3 可判定性與停機問題
§5.4 通用Turing機
§5.5 Church-Turing論題
習題
參考文獻
書單推薦
