可计算函数 作者:(俄罗斯)沈(A·Shen),(俄罗斯)韦列夏金(N·K·Vereshchagin)著;陈光还译出版时间:2014年版内容简介 这本生动、简洁的书基于作者在莫斯科大学力学数学系的本科生课程讲义,涵盖了计算的一般理论的基本概念。《可计算函数》从可计算函数的定义和一个算法开始,讨论了可判定性、可数性、通用函数、编号系统及其性质、m-完全性、不动点定理、算术分层、oracle计算、不可判定性的度。作者还介绍了一些特殊的函数模型,如Turing机和递归函数。《可计算函数》可供数学和计算机专业的本科生阅读,也可供所有希望学习计算的一般理论的基础知识的数学家和程序员使用。目录引言第一章 可计算函数、可判定集与可数集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定理:胜出条件……第八章 算术分层第九章 Turing机第十章 可计算函数的算术化第十一章 递归函数参考文献人名表索引 上一篇: 线性代数与概率论 [郑大川,吴瑞武 主编] 2012年版 下一篇: 数学实验 [冯卫兵 主编] 2013年版