**Contemporary Mathematics**

Volume: 257;
2000;
320 pp;
Softcover

MSC: Primary 03;

Print ISBN: 978-0-8218-1922-7

Product Code: CONM/257

List Price: $96.00

Individual Member Price: $76.80

**Electronic ISBN: 978-0-8218-7847-7
Product Code: CONM/257.E**

List Price: $96.00

Individual Member Price: $76.80

# Computability Theory and Its Applications: Current Trends and Open Problems

Share this page *Edited by *
*Peter A. Cholak; Steffen Lempp; Manuel Lerman; Richard A. Shore*

This collection of articles presents a snapshot of the status of
computability theory at the end of the millennium and a list of fruitful
directions for future research. The papers represent the works of experts
in the field who were invited speakers at the AMS-IMS-SIAM Joint Summer
Conference on Computability Theory and Applications held at the University of
Colorado (Boulder). The conference focused on open
problems in computability theory and on some related areas in which the
ideas, methods, and/or results of computability theory play a role.

Some presentations are narrowly focused; others cover a wider area.
Topics included from “pure” computability theory are the
computably enumerable degrees (M. Lerman), the computably enumerable
sets (P. Cholak, R. Soare), definability issues in the c.e. and Turing
degrees (A. Nies, R. Shore) and other degree structures (M. Arslanov,
S. Badaev and S. Goncharov, P. Odifreddi, A. Sorbi). The topics
involving relations between computability and other areas of logic and
mathematics are reverse mathematics and proof theory (D. Cenzer and
C. Jockusch, C. Chong and Y. Yang, H. Friedman and S. Simpson), set
theory (R. Dougherty and A. Kechris, M. Groszek, T. Slaman) and
computable mathematics and model theory (K. Ambos-Spies and A. Kučera,
R. Downey and J. Remmel, S. Goncharov and B. Khoussainov, J. Knight,
M. Peretyat'kin, A. Shlapentokh).

#### Table of Contents

# Table of Contents

## Computability Theory and Its Applications: Current Trends and Open Problems

- Contents vii8 free
- Preface ix10 free
- Program of invited talks xi12 free
- Conference participants xii13 free
- Randomness in computability theory 118 free
- Open questions about the n-c.e. degrees 1532
- The theory of numberings: Open problems 2340
- Π01 classes — structure and applications 3956
- The global structure of computably enumerable sets 6178
- Computability theory in arithmetic: Provability, structure and techniques 7390
- How many Turing degrees are there? 83100
- Questions in computable algebra and combinatorics 95112
- Issues and problems in reverse mathematics 127144
- 1. The Emergence of Reverse Mathematics 127144
- 2. The Reverse Mathematics Enterprise 129146
- 3. The Interpretability Conjecture 133150
- 4. The Coding Issue 134151
- 5. Real Analysis and Topology 135152
- 6. Banach Space Theory 137154
- 7. Ramsey Theory 137154
- 8. WQO Theory 140157
- 9. Countable Abelian Group Theory 141158
- 10. Replacing RCA0 by a Weaker Base Theory 142159
- References 143160

- Open problems in the theory of constructive algebraic systems 145162
- Independence results from ZFC in computability theory: Some open problems 171188
- Problems related to arithmetic 181198
- Embeddings into the computably enumerable degrees 191208
- Definability in the c.e. degrees: Questions and results 207224
- Strong reducibilities, again 215232
- Finitely axiomatizable theories and Lindenbaum algebras of semantic classes 221238
- Towards an analog of Hilbert's tenth problem for a number field 241258
- Natural definability in degree structures 255272
- Recursion theory in set theory 273290
- Extensions, automorphisms, and definability 279296
- Open problems in the enumeration degrees 309326

#### Readership

Graduate students and mathematicians working in or interested in computability theory and its applications.