Computability Theory and Its Applications: Current Trends and Open Problems (Proceedings of a 1999 AMS-IMS-SIAM Conference)

This Collection Of Articles Presents A Snapshot Of The Status Of Computability Theory At The End Of The Millennium And A List Of 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.--book Jacket. Randomness In Computability Theory / Klaus Ambos-spies, Antonin Kucera 1 -- Open Questions About The N-c.e. Degrees / Marat Arslanov 15 -- Theory Of Numberings: Open Problems / Serikzhan Badaev, Sergey Goncharov 23 -- [pi Superscript 0 Subscript 1] Classes--structure And Applications / Douglas Cenzer, Carl G. Jockusch, Jr. 39 -- Global Structure Of Computably Enumerable Sets / Peter A. Cholak 61 -- Computability Theory In Arithmetic: Provability, Structure And Techniques / C.t. Chong, Yue Yang 73 -- How Many Turing Degrees Are There? / Randall Dougherty, Alexander S. Kechris 83 -- Questions In Computable Algebra And Combinatorics / Rod Downey, J.b. Remmel 95 -- Issues And Problems In Reverse Mathematics / Harvey Friedman, Stephen G. Simpson 127 -- Open Problems In The Theory Of Constructive Algebraic Systems / Sergey Goncharov, Bakhadyr Khoussainov 145 -- Independence Results From Zfc In Computability Theory: Some Open Problems / Marcia Groszek 171 -- Problems Related To Arithmetic / Julia F. Knight 181 -- Embeddings Into The Computably Enumerable Degrees / Manuel Lerman 191 -- Definability In The C.e. Degrees: Questions And Results / Andre Nies 207 -- Strong Reducibilities, Again / Piergiorgio Odifreddi 215 -- Finitely Axiomatizable Theories And Lindenbaum Algebras Of Semantic Classes / Mikhail Peretyat'kin 221 -- Towards An Analog Of Hilbert's Tenth Problem For A Number Field / Alexandra Shlapentokh 241 -- Natural Definability In Degree Structures / Richard A. Shore 255 -- Recursion Theory In Set Theory / Theodore A. Slaman 273 -- Extensions, Automorphisms, And Definability / Robert I. Soare 279 -- Open Problems In The Enumeration Degrees / Andrea Sorbi 309. Peter A. Cholak ... [et Al.], Editors. Includes Bibliographical References.