递归论算法与随机性基础 PDF下载

【作　者】郝兆宽，杨睿之，杨跃著
【丛书名】逻辑与形而上学教科书系列
【形态项】 207
【出版项】 上海：复旦大学出版社 , 2018.10
【ISBN号】978-7-309-14018-7
【中图法分类号】O141.3
【主题词】递归论-高等学校-教材
【参考文献格式】 郝兆宽，杨睿之，杨跃著. 递归论. 上海：复旦大学出版社, 2018.10.
内容提要:
递归论是数理逻辑的四大分支之一，创立于20世纪30年代，它的产生源于解决数学中的判定问题。从20世纪50年代研究范围逐渐扩大，关注点从可计算性扩展到对一般意义上的复杂性、构造性和可定义性等，它与逻辑学的其他分支（如集合论、模型论和证明论）和理论计算机科学密切相关。本书是有关递归论领域基础知识的综述和导引。除了讲述图灵机、递归函数和停机问题等经典内容之外，还讨论波斯特问题及其解决，引入初步的有穷损害和无穷损害等经典的构造方法。同时，定义并讨论的图灵度和图灵归约，介绍希尔伯特第十问题，作为递归论在经典数学中一个非常典范的应用。本书对较为晚近的领域（如随机性）也进行讨论。