国外数学名著系列（影印版）31：递归可枚举集和图灵度 可计算函数与可计算生成集研究 [Recursively Enumerable Sets and Degrees:A Study of Computable Functions and Computably Generated Sets] pdf epub mobi txt 电子书 下载 2026

内容简介

　　《国外数学名著系列（影印版）31：递归可枚举集和图灵度 可计算函数与可计算生成集研究》主要内容包括：An Informal DescriptionFormal Definitions of Computable FunctionsPrimitive Recursive Functions.Diagonalization and Partial Recursive FunctionsTuring Computable FunctionsThe Basic ResultsRecursive Permutations and Myhill's Isomorphism TheoremFundamentals of Recursively Enumerable Sets and the Recursion Theorem。

内页插图

目录

Introduction
Part A． The Fundamental Concepts of Recursion Theory
Chapter Ⅰ． Recursive Functions
1． An Informal Description
2． Formal Definitions of Computable Functions
2．1． Primitive Recursive Functions
2．2． Diagonalization and Partial Recursive Functions
2．3． Turing Computable Functions
3． The Basic Results
4． Recursively Enumerable Sets and Unsolvable Problems
5． Recursive Permutations and Myhill's Isomorphism Theorem
Chapter Ⅱ． Fundamentals of Recursively Enumerable Sets and the Recursion Theorem
1． Equivalent Definitions of Recursively Enumerable Sets andTheir Basic Properties
2． Uniformity and Indices for Recursive and Finite Sets
3． The Recursion Theorem
4． Complete Sets， Productive Sets， and Creative Sets
Chapter Ⅲ． Turing Reducibility and the Jump Operator
1． Definitions of Relative Computability
2． Turing Degrees and the Jump Operator
3． The Modulus Lemma and Limit Lemma
Chapter Ⅳ． The Arithmetical Hierarchy
1． Computing Levels in the Arithmetical Hierarchy
2． Post's Theorem and the Hierarchy Theorem
3． En-Complete Sets
4． The Relativized Arithmetical Hierarchy and High and Low Degrees

Part B． Post's Problem， Oracle Constructions and the Finite Injury Priority Method
Chapter Ⅴ． Simple Sets and Post's Problem
1． Immune Sets， Simple Sets and Post's Construction
2． Hypersimple Sets and Majorizing Functions
3． The Permitting Method
4． Effectively Simple Sets Are Complete
5． A Completeness Criterion for R．E． Sets
Chapter Ⅵ． Oracle Constructions of Non-R．E． Degrees
1． A Pair of Incomparable Degrees Below 0'
2． Avoiding Cones of Degrees
3． Inverting the Jump
4． Upper and Lower Bounds for Degrees
5．* Minimal Degrees
Chapter Ⅶ． The Finite Injury Priority Method
1． Low Simple Sets
2． The Original Friedberg-Muchnik Theorem
3． SplittingTheorems

Part C． Infinitary Methods for Constructing R．E． Sets　and Degrees
Chapter Ⅷ．The Infinite Injury Priority Method
1． The Obstacles in Infinite Injury and the Thickness Lemma
2． The Injury and Window Lemmas and the Strong Thickness Lemma
3． TheJump Theorem
4． The Density Theorem and the Sacks Coding Strategy
5．*The Pinball Machine Model for Infinite Injury
Chapter Ⅸ． The Minimal Pair Method and Embedding Lattices into the R．E． Degrees
1． Minimal Pairs and Embedding the Diamond Lattice
2．* Embedding DistributiveLattices
3． The Non-Diamond Theorem
4．* Nonbranching Degrees
5．*Noncappable Degrees
Chapter Ⅹ． The Lattice of R．E． Sets Under Inclusion
……
Part D． Advanced Topics and Current Research Areas in the R．E．Degrees and the Lattice
References
Notation Index
Subject Index

前言/序言

《国外数学名著系列（影印版）31：递归可枚举集和图灵度 可计算函数与可计算生成集研究》是一本深入探讨数理逻辑核心领域的经典著作。本书以其严谨的数学结构和清晰的论述，为读者构建了一个关于递归论（Recursion Theory）的全面框架。 本书的核心内容聚焦于可计算性理论中的两个基本概念：递归可枚举集（Recursively Enumerable Sets, 简称 r.e. 集）和图灵度（Turing Degrees）。递归可枚举集，也称为半可计算集，是可计算性理论中最基本的研究对象之一，它们与可计算函数（Computable Functions）紧密相连，是判定问题（Decision Problems）的解的集合。本书系统地探讨了这些集合的结构、性质及其在可计算性层次中的位置。 图灵度，作为衡量计算复杂性的一种内在尺度，是本书的另一大支柱。图灵度通过图灵归约（Turing Reducibility）来定义，它量化了一个集合相对于另一个集合的“计算难度”。本书详细剖析了图灵度的结构，包括著名的罗杰斯定理（Rogers' Theorem）及其推论，以及图灵度在各种复杂性类之间的分布。通过对图灵度的深入研究，读者可以理解不同计算问题的相对难度，以及它们在计算宇宙中的组织方式。 本书的另一重要主题是可计算函数（Computable Functions）的研究。可计算函数是图灵机所能计算的函数的总称。本书不仅涵盖了标准的可计算函数理论，还深入探讨了它们与递归可枚举集之间的内在联系。例如，一个集合是递归可枚举的，当且仅当它是某个可计算函数的像。这种联系是理解计算本质的关键。 此外，本书还特别关注了“可计算生成集”（Computably Generated Sets）的概念。这部分内容扩展了对标准递归可枚举集的理解，探讨了那些可以通过某种计算过程逐步构造或“生成”出来的集合的性质。这涉及对构造性数学和有效数学方法的细致考察。 全书的论述风格极为专业和精确，大量采用了形式化的语言和严格的证明。作者在构建理论体系时，遵循了从基本定义到高级定理的逻辑顺序，确保了读者能够逐步掌握递归论的精髓。对于每一概念的引入，都伴随着详尽的例子和反例，以帮助理解抽象的数学结构。 本书的价值不仅在于其对基础理论的完备覆盖，还在于它对递归论各个分支的深入挖掘。读者将接触到诸如跳跃（Jumps）、可计算性谱（Computability Spectra）以及各种特殊的度结构（如低度、高优先度集等）的研究。这些高级主题对于希望在数理逻辑、计算机科学基础理论或集合论等领域进行深入研究的人来说，是不可或缺的知识储备。 作为“国外数学名著系列”的一部分，本书的影印版忠实地再现了原著的版式和内容。它的出现，为国内数学研究者提供了一个接触国际前沿数理逻辑思想的宝贵窗口。尽管主题抽象，但本书的组织结构清晰，适合具有扎实离散数学和基础代数背景的研究生和高级本科生阅读。它不仅仅是一本教科书，更是一部可以反复研读的参考工具书，为理解现代计算模型的理论极限奠定了坚实的基础。 本书的结论部分通常会展望递归论在更广泛的数学领域中的应用，例如与模型论、公理化集合论，乃至现代计算复杂性理论的交叉点。它清晰地展示了递归论如何作为一套强大的工具，来分析数学对象的内在可计算性边界。 总而言之，这部著作是关于递归可枚举集、图灵度以及可计算函数理论的权威性文献，对于任何致力于理解计算本质和形式化数学体系的学者而言，都是案头必备的经典。其内容的深度和广度，保证了它在数学逻辑领域的持久影响力。