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