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 I. 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 I. 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 1.Ideals, Filters, and Quotient Lattices 2. Splitting Theorems and Boolean Algebras 3.Maximal Sets 4.Major Subsets and r-Maximal Sets 5. Atomless r-Maximal Sets 6. Atomless hh-Simple Sets 7.* ∑3 Boolean Algebras Represented as Lattices of Supersets Chapter Ⅺ. The Relationship Between the Structure and the Degree of an R.E. Set 1. Martin's Characterization of High Degrees in Terms of Dominating Functions 2. MaximalSets and High R.E. Degrees 3. Low R.E.Sets Resemble Recursive Set 4.Non-Low2 R.E. Degrees Contain Atomless R.E. Sets 5.* Low2 R.E. Degrees Do Not Contain Atomless R.E. Sets Chapter Ⅻ. ClassifyingIndex Sets of R.E. Sets 1. Classifying the Index Set G(A)={ x : Wx =T A } 2. Classifying the Index Sets G(≤ A), G(≥ A),and G(|A) 3. Uniform Enumeration of R.E. Sets and ∑3 Index Sets 4. Classifying the Index Sets of the Highn, Lown, and Intermediate R.E.Sets 5. Fixed Points up to Turing Equivalence 6. A Generalization of the Recursion Theorem and the Completeness Criterion to All Levels of the Arithmetical Hierarchy Part D. Advanced Topics and Current Research Areas in the R.E.Degrees and the Lattice of R.E.Sets Chapter XIII. Promptly Simple Sets; Coincidence of Classes of R.E. Degrees, and an Algebraic Decomposition of the R.E. Degrees 1. Promptly Simple Setsand Degrees 2. Coincidence of the Classes of Promptly Simple Degrees, Noncappable Degrees, and Effectively Noncappable Degrees 3. A Decomposition of the R.E. Degrees Into the Disjoint Union of a Definable Ideal and a Definable Filter 4. Cuppable Degrees and the Coincidence of Promptly Simple and Low Cuppable Degrees Chapter XIV. The Tree Method and 0"'Priority Arguments 1.The Tree Method With 0'-Priority Arguments 2.The Tree Method in Priority Arguments and the Classification of 0('), 0("), and 0("')- Priority Arguments 3.The Tree Method With 0(")-Priority Arguments 3.1. Trees Applied to an Ordinary 0(")-Priority Argument 3.2. A 0"-Priority Argument Which Requires the Tree Method 4.The Tree Method With a 0("')-Priority Argument:The Lachlan Nonbounding Theorem 4.1. Preliminaries 4.2. The Basic Module for Meeting a Subrequirement 4.3. The Priority Tree 4.4. Intuition for the Priority Tree and the Proof 4.5.The Construction 4.6.The Verification Chapter XV. Automorphisms of the Lattice of R.E.Sets 1.Invariant Properties 2.Some Basic Properties of Automorphisms of ε 3. Noninvariant Properties 4. The Statement of the Extension Theorem and Its Motivation 5.Satisfying the Hypotheses of the Extension Theorem for Maximal Sets 6.The Proof of the Extension Theorem 6.1.The Machines 6.2.The Construction 6.3. The Requirements and the Motivation for the Rules 6.4. The Rules 6.5. The Verification Chapter XVI. Further Results and Open Questions About R.E. Sets and Degrees 1.Automorphisms and Isomorphisms of the Lattice of R.E. Sets 2.The Elementary Theory ofε 3. The Elementary Theory of the R.E. Degrees 4. The Algebraic Structure of tt References Notation Index SubjectIndex
京公网安备 11010102004214号