這本生動、簡潔的書基于作者在莫斯科大學(xué)力學(xué)數(shù)學(xué)系的本科生課程講義，涵蓋了計算的一般理論的基本概念。《可計算函數(shù)》從可計算函數(shù)的定義和一個算法開始，討論了可判定性、可數(shù)性、通用函數(shù)、編號系統(tǒng)及其性質(zhì)、m- 完全性、不動點定理、算術(shù)分層、oracle計算、不可判定性的度。作者還介紹了一些特殊的函數(shù)模型，如 turing機和遞歸函數(shù)。
《可計算函數(shù)》可供數(shù)學(xué)和計算機專業(yè)的本科生閱讀，也可供所有希望學(xué)習(xí)計算的一般理論的基礎(chǔ)知識的數(shù)學(xué)家和程序員使用。
目錄：
《可計算函數(shù)》
《大學(xué)生數(shù)學(xué)圖書館》叢書序
引言
第一章 可計算函數(shù)、可判定集與可數(shù)集
1.可計算函數(shù)
2.可判定集
3.可數(shù)集
4.可數(shù)集與可判定集
5.可數(shù)性與可計算性
第二章 通用函數(shù)與不可判定性
1.通用函數(shù)
2.對角構(gòu)造
3.可數(shù)的不可判定集
4.可數(shù)的不可分集
5.單集：post構(gòu)造
第三章 編號與運算
1.godel通用函數(shù)
2.可計算函數(shù)的可計算序列
3.godel通用集
第四章 godel編號系統(tǒng)的性質(zhì)
1.編號集
2.舊函數(shù)的新編號
3.godel編號系統(tǒng)的同構(gòu)
4.函數(shù)的可數(shù)性
第五章 不動點定理
1.不動點與等價關(guān)系
2.打印程序文本的程序
3.系統(tǒng)的技巧：另一個證明
4.幾點附注
第六章 m-可約性與可數(shù)集的性質(zhì)
1.m-可約性
2.m-完全集
3.m-完全性與有效不可數(shù)性
4.m-完全集的同構(gòu)
5.產(chǎn)生集
6.不可分集的對
第七章 oracle計算
1.oracle機
2.相對可計算性：等價描述
3.相對化
4.0'-計算
5.不可比集
6.friedberg-muchnik定理：構(gòu)造的一般方案
7.friedberg-muchnik定理：勝出條件
8.niedberg—muchnik定理：優(yōu)先方法
第八章 算術(shù)分層
1.類∑n和ⅱn
2.∑n和ⅱn中的通用集
3.跳躍運算
4.分層中集的分類
第九章 turing機
1.簡單的可計算模型：需要它們做什么
2.turing機：定義
3.turing機：討論
4.字問題
5.uuring機的模擬
6.thue系統(tǒng)
7.半群、生成元和關(guān)系
第十章 可計算函數(shù)的算術(shù)化
1.有限個變量的程序
2.turing機和程序
3.可計算函數(shù)是可算術(shù)化的
4.tarski定理和godel定理
5.tarski定理和godel定理的直接證明
6.算術(shù)分層和量詞交換數(shù)
第十一章 遞歸函數(shù)
1.原始遞歸函數(shù)
2.原始遞歸函數(shù)的例
3.原始遞歸集
4.遞歸的其他形式
5.turing機和原始遞歸函數(shù)
6.部分遞歸函數(shù)
7.oracle可計算性
8.生長率的估計、ackermann函數(shù)
參考文獻(xiàn)
人名表
索引
|
