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): Edward R. Griffor (ed.)
Series: Studies in Logic and the Foundations of Mathematics 140
Publisher: Elsevier
Year: 1999
Language: English
Pages: 741
Cover ......Page 1
Copyright ......Page 2
Preface ......Page 3
List of Contributors ......Page 6
Contents ......Page 7
Part 1: Fundamentals of Computability Theory ......Page 9
1. The history and concept of computability / R.I. Soare ......Page 11
2. П01 classes in recursion theory / D. Cenzer ......Page 45
Part 2: Reducibilities and Degrees ......Page 95
3. Reducibilities / P. Odifreddi ......Page 97
4. Local degree theory / S.B. Cooper ......Page 129
5. The global structure of the Turing degrees / T.A. Slaman ......Page 163
6. The recursively enumerable degrees / R.A. Shore ......Page 177
7. An overview of the computably enumerable sets / R.I. Soare ......Page 207
Part 3: Generalized Computability Theory ......Page 257
8. The continuous functionals / D. Normann ......Page 259
9. Ordinal recursion theory / C.T. Chong and S.D. Friedman ......Page 285
10. E-recursion / G.E. Sacks ......Page 309
11. Recursion on abstract structures / P.G. Hinman ......Page 323
Part 4: Mathematics and Computability Theory ......Page 369
12. Computable rings and fields / V. Stoltenberg-Hansen and J.V. Tucker ......Page 371
13. The structure of computability in analysis and physical theory: An extension of Church's thesis / M.B. Pour-El ......Page 457
14. Theory of numberings / Y.L. Ershov ......Page 481
Part 5: Logic and Computability Theory ......Page 513
15. Pure recursive model theory / T.S. Millar ......Page 515
16. Classifying recursive functions / H. Schwichtenberg ......Page 541
Part 6: Computer Science and Computability Theory ......Page 595
17. Computation models and function algebras / P. Clote ......Page 597
18. Polynomial time reducibilities and degrees / K. Ambos-Spies ......Page 691
Author Index ......Page 715
Subject Index ......Page 723
