“图灵可计算性 - 理论与应用”一书的作者（Robert I. Soare）是可计算性领域的世界权威之一。多年来，该领域的数百名讲师和教师对内容进行了彻底的课堂测试，强调可计算性的艺术，即一项需要实践的技能，同时也强调数学的审美感和品味。
简介：
图灵在 1936 年的著名论文中引入了计算机的正式定义，即图灵机。该模型既促进了实际计算机的发展，也促进了可计算性理论的发展，可计算性理论是研究机器可以计算和不能计算的内容。本书介绍了从图灵和波斯特到当前结果和方法的经典可计算性理论，以及它们在研究代数结构、模型的信息内容及其与皮亚诺算术的关系中的应用。作者将该主题描述为一门需要实践的艺术，以及所有数学家都认可的内在美的审美意义上的艺术。
第一部分从图灵机的定义到有限伤害优先论证，对可计算性的基础进行了全面的阐述。关键主题包括相对可计算性和可计算可枚举集，这些集可以有效列出但不一定能有效确定，例如皮亚诺算术定理。第二部分包括对实数的可计算开集和闭集以及有效闭集的基础和非基础定理的研究。第三部分涵盖最小图灵度。第四部分介绍游戏及其在证明定理中的应用。最后，第五部分简要介绍了可计算性理论的历史。
作者根据来自世界各地的学生、讲师和研究人员的反馈，经过数十年的磨练，内容精益求精。大多数章节都包含练习，材料根据重要性和难度精心组织。本书适合计算机科学和数学专业的高年级本科生和研究生以及从事可计算性和数理逻辑的研究人员。
Turing Computability - Theory and Applications （Robert I. Soare）
Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute. This book presents classical computability theory from Turing and Post to current results and methods, and their use in studying the information content of algebraic structures, models, and their relation to Peano arithmetic. The author presents the subject as an art to be practiced, and an art in the aesthetic sense of inherent beauty which all mathematicians recognize in their subject.
Part I gives a thorough development of the foundations of computability, from the definition of Turing machines up to finite injury priority arguments. Key topics include relative computability, and computably enumerable sets, those which can be effectively listed but not necessarily effectively decided, such as the theorems of Peano arithmetic. Part IIincludes the study of computably open and closed sets of reals and basis and nonbasis theorems for effectively closed sets. Part III covers minimal Turing degrees. Part IV is an introduction to games and their use in proving theorems. Finally, Part V offers a short history of computability theory.
The author has honed the content over decades according to feedback from students, lecturers, and researchers around the world. Most chapters include exercises, and the material is carefully structured according to importance and difficulty. The book is suitable for advanced undergraduate and graduate students in computer science and mathematics and researchers engaged with computability and mathematical logic.
参考文献：
https://link.springer.com/book/10.1007/978-3-642-31933-4
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1462800.html?mobile=1
收藏
