Computable Functions pdf epub mobi txt 電子書 下載2025
- 科普
- 計算理論
- 可計算性
- 遞歸論
- 圖靈機
- 算法
- 形式語言
- 數學邏輯
- 計算機科學
- 理論計算機科學
- 離散數學
具體描述
In 1936, before the development of modern computers, Alan Turing proposed the concept of a machine that would embody the interaction of mind, machine, and logical instruction. The idea of a 'universal machine' inspired the notion of programs stored in a computer's memory. Nowadays, the study of computable functions is a core topic taught to mathematics and computer science undergraduates. Based on the lectures for undergraduates at Moscow State University, this book presents a lively and concise introduction to the central facts and basic notions of the general theory of computation.It begins with the definition of a computable function and an algorithm and discusses decidability, enumerability, universal functions, numberings and their properties, $m$-completeness, the fixed point theorem, arithmetical hierarchy, oracle computations, and degrees of unsolvability. The authors complement the main text with over 150 problems. They also cover specific computational models, such as Turing machines and recursive functions. The intended audience includes undergraduate students majoring in mathematics or computer science, and all mathematicians and computer scientists who would like to learn basics of the general theory of computation. The book is also an ideal reference source for designing a course.
著者簡介
A. Shen: Independent University of Moscow, Moscow, Russia,
N. K. Vereshchagin: Moscow State Lomonosov University, Moscow, Russia
圖書目錄
《大學生數學圖書館》叢書序
引言
第一章 可計算函數、可判定集與可數集
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函數
參考文獻
人名錶
索引
· · · · · · (收起)
讀後感
評分
評分
評分
評分
用戶評價
相關圖書
本站所有內容均為互聯網搜索引擎提供的公開搜索信息，本站不存儲任何數據與內容，任何內容與數據均與本站無關，如有需要請聯繫相關搜索引擎包括但不限於百度，google,bing,sogou 等
© 2025 book.quotespace.org All Rights Reserved. 小美書屋 版权所有