递归可枚举集和图灵度 可计算函数与可计算生成集研究PDF电子书下载

Introduction 1

Part A.The Fundamental Concepts of Recursion Theory 5

Chapter Ⅰ.Recursive Functions 7

1.An Informal Description 7

2.Formal Definitions of Computable Functions 8

2.1.Primitive Recursive Functions 8

2.2.Diagonalization and Partial Recursive Functions 10

2.3.Turing Computable Functions 11

3.The Basic Results 14

4.Recursively Enumerable Sets and Unsolvable Problems 18

5.Recursive Permutations and Myhill’s Isomorphism Theorem 24

Chapter Ⅱ.Fundamentals of Recursively Enumerable Sets and the Recursion Theorem 27

1.Equivalent Definitions of Recursively Enumerable Sets and Their Basic Properties 27

2.Uniformity and Indices for Recursive and Finite Sets 32

3.The Recursion Theorem 36

4.Complete Sets，Productive Sets，and Creative Sets 40

Chapter Ⅲ.Turing Reducibility and the Jump Operator 46

1.Definitions of Relative Computability 46

2.Turing Degrees and the Jump Operator 52

3.The Modulus Lemma and Limit Lemma 56

Chapter Ⅳ.The Arithmetical Hierarchy 60

1.Computing Levels in the Arithmetical Hierarchy 60

2.Post’s Theorem and the Hierarchy Theorem 64

3.∑n-Complete Sets 65

4.The Relativized Arithmetical Hierarchy and High and Low Degrees 69

Part B.Post’s Problem，Oracle Constructions and the Finite Injury Priority Method 75

Chapter Ⅴ.Simple Sets and Post’s Problem 77

1.Immune Sets，Simple Sets and Post’s Construction 77

2.Hypersimple Sets and Majorizing Functions 80

3.The Permitting Method 84

4.Effectively Simple Sets Are Complete 87

5.A Completeness Criterion for R.E.Sets 88

Chapter Ⅵ.Oracle Constructions of Non-R.E.Degrees 92

1.A Pair of Incomparable Degrees Below 0′ 93

2.Avoiding Cones of Degrees 96

3.Inverting the Jump 97

4.Upper and Lower Bounds for Degrees 100

5.Minimal Degrees 103

Chapter Ⅶ.The Finite Injury Priority Method 110

1.Low Simple Sets 110

2.The Original Friedberg-Muchnik Theorem 118

3.Splitting Theorems 121

Part C.Infinitary Methods for Constructing R.E.Sets and Degrees 127

Chapter Ⅷ.The Infinite Injury Priority Method 129

1.The Obstacles in Infinite Injury and the Thickness Lemma 130

2.The Injury and Window Lemmas and the Strong Thickness Lemma 134

3.The Jump Theorem 137

4.The Density Theorem and the Sacks Coding Strategy 142

5.The Pinball Machine Model for Infinite Injury 147

Chapter Ⅸ The Minimal Pair Method and Embedding Lattices into the R.E.Degrees 151

1.Minimal Pairs and Embedding the Diamond Lattice 152

2.Embedding Distributive Lattices 157

3.The Non-Diamond Theorem 161

4.Nonbranching Degrees 168

5.Noncappable Degrees 174

Chapter Ⅹ.The Lattice of R.E.Sets Under Inclusion 178

1.Ideals，Filters，and Quotient Lattices 178

2.Splitting Theorems and Boolean Algebras 181

3.Maximal Sets 187

4.Major Subsets and r-Maximal Sets 190

5.Atomless r-Maximal Sets 195

6.Atomless hh-Simple Sets 199

7.∑3 Boolean Algebras Represented as Lattices of Supersets 203

Chapter Ⅺ The Relationship Between the Structure and the Degree of an R.E.Set 207

1.Martin’s Characterization of High Degrees in Terms of Dominating Functions 207

2.Maximal Sets and High R.E.Degrees 215

3.Low R.E.Sets Resemble Recursive Sets 224

4.Non-Low2 R.E.Degrees Contain Atomless R.E.Sets 230

5.Low2 R.E.Degrees Do Not Contain Atomless R.E.Sets 233

Chapter Ⅻ.Classifying Index Sets of R.E.Sets 241

1.Classifying the Index Set G（A）＝{x：Wx？TA} 242

2.Classifying the Index Sets G（≤A），G（≥A），and G（|A） 246

3.Uniform Enumeration of R.E.Sets and ∑3 Index Sets 253

4.Classifying the Index Sets of the High n，Low n，and Intermediate R.E.Sets 259

5.Fixed Points up to Turing Equivalence 270

6.A Generalization of the Recursion Theorem and the Completeness Criterion to All Levels of the Arithmetical Hierarchy 272

Part D.Advanced Topics and Current Research Areas in the R.E. Degrees and the Lattice of R.E.Sets 279

Chapter ⅩⅢ.Promptly Simple Sets，Coincidence of Classes of R.E.Degrees，and an Algebraic Decomposition of the R.E.Degrees 281

1.Promptly Simple Sets and Degrees 282

2.Coincidence of the Classes of Promptly Simple Degrees，Noncappable Degrees，and Effectively Noncappable Degrees 288

3.A Decomposition of the R.E.Degrees Into the Disjoint Union of a Definable Ideal and a Definable Filter 294

4.Cuppable Degrees and the Coincidence of Promptly Simple and Low Cuppable Degrees 296

Chapter ⅩⅣ.The Tree Method and 0？-Priority Arguments 300

1.The Tree Method With 0′-Priority Arguments 301

2.The Tree Method in Priority Arguments and the Classification of 0′，0″，and 0？-Priority Arguments 304

3.The Tree Method With 0″-Priority Arguments 308

3.1.Trees Applied to an Ordinary 0″-Priority Argument 308

3.2.A 0″-Priority Argument Which Requires the Tree Method 309

4.The Tree Method With a 0？-Priority Argument：The Lachlan Nonbounding Theorem 315

4.1.Preliminaries 315

4.2.The Basic Module for Meeting a Subrequirement 316

4.3.The Priority Tree 320

4.4.Intuition for the Priority Tree and the Proof 325

4.5.The Construction 327

4.6.The Verification 331

Chapter ⅩⅤ.Automorphisms of the Lattice of R.E.Sets 338

1.Invariant Properties 338

2.Some Basic Properties of Automorphisms of ε 341

3.Noninvariant Properties 345

4.The Statement of the Extension Theorem and Its Motivation 348

5.Satisfying the Hypotheses of the Extension Theorem for Maximal Sets 354

6.The Proof of the Extension Theorem 359

6.1.The Machines 359

6.2.The Construction 362

6.3.The Requirements and the Motivation for the Rules 363

6.4.The Rules 365

6.5.The Verification 368

Chapter ⅩⅥ.Further Results and Open Questions About R.E.Sets and Degrees 374

1.Automorphisms and Isomorphisms of the Lattice of R.E.Sets 374

2.The Elementary Theory of ε 379

3.The Elementary Theory of the R.E.Degrees 383

4.The Algebraic Structure of R 385

References 389

Notation Index 419

Subject Index 429