Robert Soare's New Book:

Computability Theory and Applications [CTA]

under contract with Springer-Verlag.

Soare's former book Computably Enumerable Sets and Degrees, Springer-Verlag, 1987, has been a standard text and research reference on computability for over twenty years. The new book [Soare, CTA] will include all of this previous material and much more. The field of computability from the mid 1950's through the 1980's was primarily concerned with certain topics arising from the Post program [1944] which focused on Turing degrees and the properties of computably enumerable (c.e.) sets and degrees. Although these topics are still important and will be covered, many other topics have been added in the last twenty to thirty years including $\Pi^0_1$ classes, computable model theory, computable algebraic structures, forcing, randomness and Kolmogorov complexity, applications to differential geometry, and many more topics.

The core of [CTA] will be Part I and Part II of fifteen to twenty chapters covering most of the material in Soare [1987] but in completely rewritten form. These parts will be suitable for for a two quarter or two semester course which is an introduction to computability for graduate students or advanced undergraduates. Parts III and IV will include special topics in computability, and applications of computability to a wide variety of other areas in logic, and other areas of mathematics, reflecting the widening interaction of comptability with other areas.

The first seven or eight chapters were written from June, 2005 to May, 2006 and were presented in several graduate courses at Chicago, Berkeley, Cornell, Notre Dame, and elsewhere. These chapters have temporarily been removed from the web page while they are under revision and the subsequent chapters in Part 2 are being written.

The newbook is currently under revision. If you need a preliminary copy for teaching or research, please email Robert Soare.