Computable Functions pdf epub mobi txt 电子书 下载 2026
- 科普
- 计算理论
- 可计算性
- 递归论
- 图灵机
- 算法
- 形式语言
- 数学逻辑
- 计算机科学
- 理论计算机科学
- 离散数学
具体描述
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 等
© 2026 book.wenda123.org All Rights Reserved. 图书目录大全 版权所有