大學生數學圖書館4：可計算函式

內容簡介

《大學生數學圖書館4:可計算函式》生動、簡潔的書基於作者在莫斯科大學力學數學系的本科生課程講義，涵蓋了計算的一般理論的基本概念。沈、韋列夏金著，陳光還譯的《可計算函式》從可計算函式的定義和一個算法開始，討論了可判定性、可數性、通用函式、編號系統及其性質、m—完全性、不動點定理、算術分層、oracle計算、不可判定性的度。

《大學生數學圖書館4:可計算函式》共分十一章，內容包括通用函式與不可判定性、編號與運算、Godel編號系統的性質、不動點定理、m—可約性與可數集的性質、Oracle計算、算術分層等。此外，作者還介紹了一些特殊的函式模型，如Turing機和遞歸函式。

作者簡介

作者：（俄羅斯）沈（A.Shen）（俄羅斯）韋列夏金（N.K.Vereshchagin）譯者：陳光還

圖書目錄

《大學生數學圖書館》叢書序
引言
第一章可計算函式、可判定集與可數集
1.可計算函式
2.可判定集
3.可數集
4.可數集與可判定集
5.可數性與可計算性
第二章通用函式與不可判定性
1.通用函式
2.對角構造
3.可數的不可判定集
4.可數的不可分集
5.單集：Post構造
第三章編號與運算
1.Godel通用函式
2.可計算函式的可計算序列
3.Godel通用集
第四章Godel編號系統的性質
1.編號集
2.舊函式的新編號
3.Godel編號系統的同構
4.函式的可數性
第五章不動點定理
1.不動點與等價關係
2.列印程式文本的程式
3.系統的技巧：另一個證明
4.幾點附註
第六章m—可約性與可數集的性質
1.m—可約性
2.m—完全集
3.m—完全性與有效不可數性
4.m—完全集的同構
5.產生集
6.不可分集的對
第七章Oracle計算
1.Oracle機
2.相對可計算性：等價描述
3.相對化
4.0'—計算
5.不可比集
6.Friedberg—Muchnik定理：構造的一般方案
7.Friedberg—Muchnik定理：勝出條件
8.niedberg—Muchnik定理：優先方法
第八章算術分層
1.類∑n和Ⅱn
2.∑n和Ⅱn中的通用集
3.跳躍運算
4.分層中集的分類
第九章Turing機
1.簡單的可計算模型：需要它們做什麼
2.Turing機：定義
3.Turing機：討論
4.字問題
5.Uuring機的模擬
6.Thue系統
7.半群、生成元和關係
第十章可計算函式的算術化
1.有限個變數的程式
2.Turing機和程式
3.可計算函式是可算術化的
4.Tarski定理和Godel定理
5.Tarski定理和Godel定理的直接證明
6.算術分層和量詞交換數
第十一章遞歸函式
1.原始遞歸函式
2.原始遞歸函式的例
3.原始遞歸集
4.遞歸的其他形式
5.Turing機和原始遞歸函式
6.部分遞歸函式
7.Oracle可計算性
8.生長率的估計、Ackermann函式
參考文獻
人名表
索引

大學生數學圖書館4：可計算函式

基本介紹

內容簡介

作者簡介

圖書目錄

相關詞條

熱門詞條