The Art of Classical Computability [CTA]

Frontice.pdf of Soare's new book CTA .

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 CTA
[Soare, 2012] 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. Volume 1 will appear in 2012, in time
for the celebration of the Turing Centennial, and will be in several
parts.

Muchnik [1956] and Friedberg [1957] invented a * computable
approximation * to this forcing argument, called the * finite
injury method *, where they allow a requirement to finitely often
be * injured * (i.e, previous progress to be destroyed), and then
they begin again to satisfy the given requirement, until after it is
finally satisfied and never injured thereafter. We present finite
injury priority arguments and a solution to Post's problem of
c.e. sets A and B of incomparable Turing degree.

These chapters are suitable for a one semester introductory course for graduate students or advanced undergraduates in mathematics or computer science. The student who has mastered Part~I will have a good grasp of the fundamentals of computability, such as often required on Ph.D. exams, and will be able to apply computability theory to complexity theory and other parts of mathematical logic.

By the end of the initial period of computability 1930--1970 the
constructions and proofs had become so complicated that it had become
very difficult to obtain any intuition about them. Fortunately,
Lachlan introduced: (1) the method of * games in computability *
Lachlan [1970a] (see Chapter on Lachlan Games); (2) the topology of
priority arguments Lachlan [1973], which gave rise to the * true
stages method * for infinite injury (refined in Chapter 8); and (3)
the use * trees * in Lachlan [1975] to divide a strategy for a
priority argument into a collection of strategies, one assigned to
each node of the tree, and each equipped with a guess about the
outcome of higher priority strategies. Lachlan's original use of
trees [1975] for a 0''' arugment was very complicated, but the tree
method with simplifications was presented in Soare [1985] and is
further refined in this book in Chapters 9 and 10. It has been used
very extensively in computability theory ever since. These three
improvements and their refinements allow the reader of this book to
help keep in mind what Leo Harrington calls the {\em mountaintop view}
of the proof: a small number of key elements, their interaction, how
we resolve conflicts between conflicting requirements, and the
underlying beauty of the proof.

This material is suitable for a second semester course in computability theory. The student who has mastered this material will be a more serious student, interested in understanding the classic methods in computability over the last fifty years. These methods and results are often used and quoted in research papers and lectures. The material is presented in a intuitive fashion tailored to the serious student.