Robert Soare's New Book:
Computability Theory and Applications
The Art of Classical Computability
[CTA]
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, presented in
a more modern and intuitive fashion. The book will appear in two
volumes for an earlier publication. Volume 1 will be in five parts:
Part 1 on the fundamentals of computability and finitary
constructions, through the finite injury constructions. Part 2 will
cover infinitary constructions, the Sacks Jump and Density Theorems,
the minimal pair method, trees used in priority constructions. Part 3
will be on additional fundamental topics such as high and low degrees
and promptly simple sets and degrees, Part 4 on games in computability theory,
and Part 5 on applications of computability.
These there parts include the
material for most one year graduate courses in computability and the
material most graduate students need for their research.
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,
applications to differential geometry, and many more topics.
The book is scheduled to appear in early 2012 in time for
the Turing centennial. It can be ordered in 2012
from Springer-Verlag.