9780821819227

Computability Theory and Its Applications: Current Trends and Open Problems : Proceedings of a 1999 Ams-Ims-Siam, Joint Summer Research Conference, Computability Theory and Applications, June

by
  • ISBN13:

    9780821819227

  • ISBN10:

    0821819224

  • Format: Paperback
  • Copyright: 2000-06-01
  • Publisher: Amer Mathematical Society

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

Purchase Benefits

  • Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
List Price: $96.00 Save up to $9.60
  • Rent Book $86.40
    Add to Cart Free Shipping

    TERM
    PRICE
    DUE

Supplemental Materials

What is included with this book?

  • The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
  • The Rental copy of this book is not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Summary

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

Preface ix
Program of invited talks xi
Conference participants xii
Randomness in computability theory
1(14)
Klaus Ambos-Spies
Antonin Kucera
Open questions about the n-c.e. degrees
15(8)
Marat Arslanov
The theory of numberings: Open problems
23(16)
Serikzhan Badaev
Sergey Goncharov
Π01 classes---structure and applications
39(22)
Douglas Cenzer
Carl G. Jockusch, Jr.
The global structure of computably enumerable sets
61(12)
Peter A. Cholak
Computability theory in arithmetic: Provability, structure and techniques
73(10)
C. T. Chong
Yue Yang
How many Turing degrees are there?
83(12)
Randall Dougherty
Alexander S. Kechris
Questions in computable algebra and combinatorics
95(32)
Rod Downey
J. B. Remmel
Issues and problems in reverse mathematics
127(18)
Harvey Friedman
Stephen G. Simpson
Open problems in the theory of constructive algebraic systems
145(26)
Sergey Goncharov
Bakhadyr Khoussainov
Independence results from ZFC in computability theory: Some open problems
171(10)
Marcia Groszek
Problems related to arithmetic
181(10)
Julia F. Knight
Embeddings into the computably enumerable degrees
191(16)
Manuel Lerman
Definability in the c.e. degrees: Questions and results
207(8)
Andre Nies
Strong reducibilities, again
215(6)
Piergiorgio Odifreddi
Finitely axiomatizable theories and Lindenbaum algebras of semantic classes
221(20)
Mikhail Peretyat'kin
Towards an analog of Hilbert's tenth problem for a number field
241(14)
Alexandra Shlapentokh
Natural definability in degree structures
255(18)
Richard A. Shore
Recursion theory in set theory
273(6)
Theodore A. Slaman
Extensions, automorphisms, and definability
279(30)
Robert I. Soare
Open problems in the enumeration degrees
309
Andrea Sorbi

Rewards Program

Write a Review