AMS Bookstore LOGO amslogo
Return to List

AMS TextbooksAMS Applications-related Books

Computability Theory and Its Applications: Current Trends and Open Problems
Edited by: Peter A. Cholak, University of Notre Dame, IN, Steffen Lempp, University of Wisconsin, Madison, WI, Manuel Lerman, University of Connecticut, Storrs, CT, and Richard A. Shore, Cornell University, Ithaca, NY

Contemporary Mathematics
2000; 320 pp; softcover
Volume: 257
ISBN-10: 0-8218-1922-4
ISBN-13: 978-0-8218-1922-7
List Price: US$91
Member Price: US$72.80
Order Code: CONM/257
[Add Item]

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).


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

Table of Contents

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

  AMS Home | Comments:
© Copyright 2014, American Mathematical Society
Privacy Statement

AMS Social

AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia