递归可枚举集和图灵度 可计算函数与可计算生成集研究【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Introduction1

Part A.The Fundamental Concepts of Recursion Theory5

Chapter Ⅰ.Recursive Functions7

1.An Informal Description7

2.Formal Definitions of Computable Functions8

2.1.Primitive Recursive Functions8

2.2.Diagonalization and Partial Recursive Functions10

2.3.Turing Computable Functions11

3.The Basic Results14

4.Recursively Enumerable Sets and Unsolvable Problems18

5.Recursive Permutations and Myhill’s Isomorphism Theorem24

Chapter Ⅱ.Fundamentals of Recursively Enumerable Sets and the Recursion Theorem27

1.Equivalent Definitions of Recursively Enumerable Sets and Their Basic Properties27

2.Uniformity and Indices for Recursive and Finite Sets32

3.The Recursion Theorem36

4.Complete Sets，Productive Sets，and Creative Sets40

Chapter Ⅲ.Turing Reducibility and the Jump Operator46

1.Definitions of Relative Computability46

2.Turing Degrees and the Jump Operator52

3.The Modulus Lemma and Limit Lemma56

Chapter Ⅳ.The Arithmetical Hierarchy60

1.Computing Levels in the Arithmetical Hierarchy60

2.Post’s Theorem and the Hierarchy Theorem64

3.∑n-Complete Sets65

4.The Relativized Arithmetical Hierarchy and High and Low Degrees69

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

Chapter Ⅴ.Simple Sets and Post’s Problem77

1.Immune Sets，Simple Sets and Post’s Construction77

2.Hypersimple Sets and Majorizing Functions80

3.The Permitting Method84

4.Effectively Simple Sets Are Complete87

5.A Completeness Criterion for R.E.Sets88

Chapter Ⅵ.Oracle Constructions of Non-R.E.Degrees92

1.A Pair of Incomparable Degrees Below 0′93

2.Avoiding Cones of Degrees96

3.Inverting the Jump97

4.Upper and Lower Bounds for Degrees100

5.Minimal Degrees103

Chapter Ⅶ.The Finite Injury Priority Method110

1.Low Simple Sets110

2.The Original Friedberg-Muchnik Theorem118

3.Splitting Theorems121

Part C.Infinitary Methods for Constructing R.E.Sets and Degrees127

Chapter Ⅷ.The Infinite Injury Priority Method129

1.The Obstacles in Infinite Injury and the Thickness Lemma130

2.The Injury and Window Lemmas and the Strong Thickness Lemma134

3.The Jump Theorem137

4.The Density Theorem and the Sacks Coding Strategy142

5.The Pinball Machine Model for Infinite Injury147

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

1.Minimal Pairs and Embedding the Diamond Lattice152

2.Embedding Distributive Lattices157

3.The Non-Diamond Theorem161

4.Nonbranching Degrees168

5.Noncappable Degrees174

Chapter Ⅹ.The Lattice of R.E.Sets Under Inclusion178

1.Ideals，Filters，and Quotient Lattices178

2.Splitting Theorems and Boolean Algebras181

3.Maximal Sets187

4.Major Subsets and r-Maximal Sets190

5.Atomless r-Maximal Sets195

6.Atomless hh-Simple Sets199

7.∑3 Boolean Algebras Represented as Lattices of Supersets203

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

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

2.Maximal Sets and High R.E.Degrees215

3.Low R.E.Sets Resemble Recursive Sets224

4.Non-Low2 R.E.Degrees Contain Atomless R.E.Sets230

5.Low2 R.E.Degrees Do Not Contain Atomless R.E.Sets233

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

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 Sets253

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

5.Fixed Points up to Turing Equivalence270

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

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

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

1.Promptly Simple Sets and Degrees282

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

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

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

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

1.The Tree Method With 0′-Priority Arguments301

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

3.The Tree Method With 0″-Priority Arguments308

3.1.Trees Applied to an Ordinary 0″-Priority Argument308

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

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

4.1.Preliminaries315

4.2.The Basic Module for Meeting a Subrequirement316

4.3.The Priority Tree320

4.4.Intuition for the Priority Tree and the Proof325

4.5.The Construction327

4.6.The Verification331

Chapter ⅩⅤ.Automorphisms of the Lattice of R.E.Sets338

1.Invariant Properties338

2.Some Basic Properties of Automorphisms of ε341

3.Noninvariant Properties345

4.The Statement of the Extension Theorem and Its Motivation348

5.Satisfying the Hypotheses of the Extension Theorem for Maximal Sets354

6.The Proof of the Extension Theorem359

6.1.The Machines359

6.2.The Construction362

6.3.The Requirements and the Motivation for the Rules363

6.4.The Rules365

6.5.The Verification368

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

1.Automorphisms and Isomorphisms of the Lattice of R.E.Sets374

2.The Elementary Theory of ε379

3.The Elementary Theory of the R.E.Degrees383

4.The Algebraic Structure of R385

References389

Notation Index419

Subject Index429