The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey of recent results (due to the complexity of the methods and proofs themselves). Hence the variation in level of presentation from chapter to chapter only reflects the conceptual situation itself. One example of this is the collective efforts to develop an acceptable theory of computation on the real numbers. The last two decades has seen at least two new definitions of effective operations on the real numbers.
Author(s): E.R. Griffor
Series: Studies in Logic and the Foundations of Mathematics 140
Publisher: North Holland
Year: 1999
Language: English
Commentary: front matter missing
Pages: 706
Preface......Page 1
1. The History and Concept of Computability - Soare......Page 5
1. Introduction......Page 7
1. The concepts of computability and recursion......Page 8
2. The origin of recursion......Page 9
4. General recursive functions......Page 10
5. The flaw in Church's thesis......Page 11
1. Turing's idealized human computor......Page 13
2. Accepting Turing's Thesis......Page 15
3. The Church-Turing Thesis as a definition......Page 17
4. Other theses became definitions......Page 18
5. Register machines......Page 19
1. Kleene's normal form and his μ-recursive functions......Page 20
2. Computably enumerable sets and Post......Page 21
3. History of relative computability......Page 23
4. Higher order computability......Page 24
5. How the terms became fixed......Page 26
6. Current usage of the concepts and terms......Page 27
5. Mathematical, scientific and general English usage......Page 30
6. Themes and goals of computability theory......Page 31
7. Analysis......Page 32
References......Page 33
2. Π^0_1 Classes in Computability Theory - Cenzer......Page 39
1. Background......Page 40
2. Preliminaries......Page 42
2. Π^0_1 sets and classes......Page 46
3. Basis and anti-basis results......Page 53
4. Cantor-Bendixson rank......Page 63
5. Minimal and thin classes......Page 71
1. Logical theories......Page 76
2. Graph-coloring problems......Page 81
References......Page 84
3. Reducibilities - Odifreddi......Page 88
2. ... to recursion theory......Page 89
1. Many-one degrees......Page 90
1. Algebraic global structure......Page 92
2. Algebraic local structure......Page 94
3. Metamathematical properties......Page 95
2. Truth-table degrees......Page 97
1. Truth-table reducibilities......Page 98
2. Global structure......Page 101
3. Local structure......Page 103
3. Enumeration degrees......Page 104
1. Global structure......Page 105
2. Local structure......Page 106
4. Progress on the problems of "Strong Reducibilities"......Page 107
1. Truth-table degrees......Page 111
2. Recursively enumerable truth-table degrees......Page 112
3. Enumeration degrees......Page 113
References......Page 114
4. Local Degree Theory - Cooper......Page 119
1. Logic, hierarchies and approximations......Page 121
2. Decidability and forcing below 0'......Page 122
3. Deconstructing constructions: 1-generic degrees......Page 124
4. Structure, jump and definability......Page 126
5. Definability in cones......Page 129
6. Degree and information content......Page 131
7. The Ershov hierarchy for D(≤0')......Page 135
8. Automorphisms and undefinability......Page 138
9. Enumeration and Turing reducibilities: The local theory......Page 140
References......Page 143
5. The Global Structure of the Turing Degrees - Slaman......Page 152
2. Initial segments......Page 154
2. Coding and definability theorems......Page 155
2. Coding in D and undecidability......Page 156
3. Shore's program......Page 157
4. Cooper's definition of the Turing jump......Page 158
3. Global definability and biinterpretability......Page 159
1. Biinterpretability with parameters......Page 161
4. Automorphisms......Page 162
References......Page 163
6. The Recursively Enumerable Degrees - Shore......Page 166
1. Introduction......Page 167
2. Structure and decidability......Page 168
3. Undecidability and beyond......Page 177
4. Natural definability......Page 185
References......Page 190
7. An Overview of the Computably Enumerable Sets - Soare......Page 195
1. A brief history of c.e. sets......Page 196
2. Definable properties of c.e. sets......Page 198
1. Creative sets......Page 199
2. Incomplete sets......Page 201
3. Complete sets......Page 204
4. Nonlow sets......Page 207
1. Some results on automorphisms......Page 212
2. A sketch of the Δ^0_3-automorphism method......Page 216
3. The automorphism theorem......Page 230
4. Using that A is noncomputable to obtain the set C_α of coding states......Page 231
5. Moving α-witnesses into B......Page 233
6. Appointing α-witnesses and Step 7......Page 234
7. Coding states C_α and Step 8......Page 235
8. The Coding Theorem......Page 236
4. Invariance......Page 237
5. Decidability and undecidability......Page 238
References......Page 240
8. The Continuous Functionals - Normann......Page 245
1. Some elements from the history......Page 246
2. The functionals......Page 247
3. Complexity......Page 250
4. Computations......Page 252
5. The fan functional......Page 256
6. Bar recursion......Page 259
7. Associates......Page 260
8. The finitary aspects......Page 262
9. Functional interpretation of analysis......Page 265
References......Page 268
9. Ordinal Recursion Theory - Chong & Friedman......Page 270
1. α-recursion theory......Page 271
2. Definability......Page 273
3. The α-finite injury priority method......Page 275
4. The Density Theorem......Page 277
5. Non-existence of maximal sets......Page 279
6. Post's problem above 0' and set-theoretic methods......Page 281
7. Applications to fragments of Peano Arithmetic......Page 282
2. β-recursion theory......Page 283
3. The admissibility spectrum......Page 286
References......Page 290
10. E-recursion - Sacks......Page 293
11. Recursion on Abstract Structures - Hinman......Page 307
1. Introduction......Page 308
2. Structures and functionals......Page 310
3. Register machines over first-order structures......Page 315
4. Recursion......Page 318
5. The main examples......Page 323
6. Structures with arithmetic......Page 331
7. Sections and envelopes......Page 336
8. Appendix......Page 346
References......Page 349
12. Computable Rings and Fields - Stoltenberg-Hansen & Tucker......Page 352
1. Introduction......Page 354
1. Computable algebraic structures......Page 355
2. Historical notes on computable rings and fields......Page 358
3. Structure and prerequisites......Page 360
1. Primary definitions......Page 361
2. Invariance......Page 367
3. Subrings and ideals......Page 373
4. Direct sums and limits......Page 376
1. Field extensions......Page 380
2. Splitting algorithms......Page 388
3. Algebraically closed fields......Page 392
4. Some undecidable problems......Page 394
4. Computable Noetherian rings......Page 397
1. Noetherian rings and modules......Page 398
2. Computable coherence......Page 399
3. The ideal membership relation......Page 402
4. Polynomial rings......Page 406
1. Computable groups......Page 410
2. Linear algebra......Page 413
4. Computable universal algebras......Page 415
5. Algebraic theory of data in computer science......Page 416
7. Computable numbers......Page 417
8. General algebraic framework for computations on algebras......Page 418
9. Primitive recursive algebra......Page 419
10. Polynomial-time algebras......Page 420
11. Generalised computability theories and exact computation in uncountable algebras......Page 421
12. Computable approximations of topological algebras......Page 422
13. Constructive algebra......Page 423
References......Page 424
13. The Structure of Computability in Analysis and Physical Theory: An Extension of Church's Thesis - Pour-El......Page 437
1. Introduction......Page 438
1. Introduction......Page 440
2. Computable reals and sequences of reals......Page 441
3. Computability for continuous functions......Page 443
4. Computability and physical theory: wave propagation & heat dissipation......Page 447
5. L^p computability......Page 448
2. The computability structure......Page 450
3. The First Main Theorem, statement and applications......Page 454
4. The Second Main Theorem, the Eigenvector Theorem and related results......Page 456
References......Page 458
14. Theory of Numberings - Ershov......Page 460
Introduction......Page 461
1. Basic Notions......Page 464
2. Computable numberings......Page 473
1. Index sets......Page 482
2. Creativity and m-universality......Page 486
3. Numbered sets with approximation and the problem P......Page 487
References......Page 489
15. Pure Recursive Model Theory - Millar......Page 491
1. Introduction......Page 492
1. Strong similarities......Page 493
2. Weak similarities......Page 496
3. Differences......Page 498
3. Computational hierarchies of model theoretic domains......Page 501
2. Homogeneous models revisited......Page 502
3. Ehrenfeucht theories......Page 504
1. Almost homogeneity......Page 505
2. Ehrenfeucht theories and stability......Page 506
3. Omitting types revisited......Page 508
4. Number of countable models......Page 509
5. An Ash legacy......Page 513
References......Page 514
16. Classifying Recursive Functions - Schwichtenberg......Page 517
1. Introduction......Page 518
2. Collapsing results......Page 520
3. The extended Grzegorczyk hierarchy......Page 524
4. Partial continuous functionals......Page 526
5. Computability in higher types......Page 542
6. Bounded fixed point operators......Page 553
7. Elimination of detours through higher types by transfinite recursion......Page 560
References......Page 566
17. Computation Models and Function Algebras - Clote......Page 571
1. Introduction......Page 572
1. Turing machines......Page 574
2. Parallel machine model......Page 584
3. Circuit families......Page 587
3. Some recursion schemes......Page 590
1. An algebra for the logtime hierarchy LH......Page 591
2. Bounded recursion on notation......Page 604
3. Bounded recursion......Page 607
4. Bounded minimization......Page 614
5. Divide and conquer, course-of-value and miscellaneous......Page 620
6. Safe recursion......Page 628
4. Type 2 functionals......Page 638
Note added in proof......Page 651
References......Page 652
List of symbols......Page 660
18. Polynomial Time Reducibilities and Degrees - Ambos-Spies......Page 664
1. Introduction......Page 665
2. Basic definitions and results......Page 666
3. The meet operator and gap languages......Page 669
4. Delayed diagonalization or the looking back technique......Page 671
5. The iterated look-ahead technique......Page 674
6. The theory of the polynomial time degrees......Page 677
7. Other reducibilities and the axiomatic approach......Page 681
References......Page 683
Author Index......Page 687
Subject Index......Page 694
