計算模型導引

《計算模型導引》是2012年出版的圖書，作者是宋方敏。主要介紹了計算模型領域的主要概念，方法和技術，旨在通過介紹遞歸函式，Lambda演算和Turing機來理解計算理論。

基本介紹

• 中文名：計算模型導引
• 作者： 宋方敏
• 頁數： 151
• ISBN： 9787040347371

版權資訊

作者: 宋方敏; 出版年: 2012-6; 頁數: 151; 定價: 24.00元; ISBN: 9787040347371

內容簡介

本課程講述如下專題：遞歸函式、算盤機、Lambda演算、Turing機和Church論題。計算理論是計算機科學的理論基礎。 書中每章附有適量習題，供讀者選做。

目錄

第一章 遞歸函式

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.4 Church-Rosser定理

3.5 不動點定理

3.6 遞歸函式的λ-可定義性

3.7 與遞歸論對應的結果

習題

第四章 組合邏輯

4.1 組合子的形式系統

4.2 弱歸約

4.3 CL與 λ的對應

習題

第五章 Turing 機

5.1 Turing 機的形式描述

5.2 Turing 機的計算能力

5.3 可判定性與停機問題

5.4 通用Turing 機

5.5 Church-Turing 論題

習題

參考文獻