Computability Theory and Its Applications: Current Trends and Open Problems(Contemporary Mathematics)

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 1999 Summer Conference on Computability Theory and Applications, which 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. Kucera, R. Downey and J. Remmel, S. Goncharov and B. Khoussainov, J. Knight, M. Peretyat'kin, A. Shlapentokh).

Table of Contents:
Randomness in computability theory by K. Ambos-Spies and A. Kucera Open questions about the $n$-c.e. degrees by M. Arslanov The theory of numberings: Open problems by S. Badaev and S. Goncharov $\mathrm{\Pi}^0_1$ classes -- Structure and applications by D. Cenzer and C. G. Jockusch, Jr. The global structure of computably enumerable sets by P. A. Cholak Computability theory in arithmetic: Provability, structure and techniques by C. T. Chong and Y. Yang How many Turing degrees are there? by R. Dougherty and A. S. Kechris Questions in computable algebra and combinatorics by R. Downey and J. B. Remmel Issues and problems in reverse mathematics by H. Friedman and S. G. Simpson Open problems in the theory of constructive algebraic systems by S. Goncharov and B. Khoussainov Independence results from ZFC in computability theory: Some open problems by M. Groszek Problems related to arithmetic by J. F. Knight Embeddings into the computably enumerable degrees by M. Lerman Definability in the c.e. degrees: Questions and results by A. Nies Strong reducibilities, again by P. Odifreddi Finitely axiomatizable theories and Lindenbaum algebras of semantic classes by M. Peretyat'kin Towards an analog of Hilbert's tenth problem for a number field by A. Shlapentokh Natural definability in degree structures by R. A. Shore Recursion theory in set theory by T. A. Slaman Extensions, automorphisms, and definability by R. I. Soare Open problems in the enumeration degrees by A. Sorbi.