Robert Soare's New Book:

Computability Theory and Applications:
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.

Part I. Foundations Of Computability: Chapters 1-7

Part I of CTA includes Chapters 1-7, and contains the basic material that most people seek if they are learning computability for the first time. It begins with the definition of computable functions in the 1930's by Turing, Church, Goedel, Post, and Kleene and the properties of computably enumerable (c.e.) sets. It covers the Kleene-Post [1954] finite extension (finite forcing) argument.

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.

Part II. Infinite Injury and the Tree Method: Chapters 8-10

Shoenfield [1961] and Sacks independently [1963a,b,c] invented the infinite injury method for computable constructions in which a given requirement may be injured infinitely often, but only computably so, and still somehow succeed. Yates, Martin, and Lachlan extended and refined this method and added others such as the minimal pair construction of a pair of noncomputable c.e. sets A and B whose degree have infimum degree 0 the degree of the computable sets.

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.

Part III. Games in Computability Theory

In Part III we consider some games which shed light on computability and serve as a useful tool to discover and present theorems. The Banach-Mazur games had been used decades ago in point set topology to study dense open sets. They are used here to study the finite extension constructions presented in Chapter 6 and to help give a paradigm there to analyze extension constructions. Banach-Mazur games are useful when we are doing a construction computably in an oracle, but when we are constructing computably enumerable (c.e.) sets the construction must be completely decidable with \emph{no oracle}. Lachlan [1970] invented a new kind of game, now called a Lachlan game to handle computable constructions. In a Lachlan game there are two players, Player I (RED), and Player II (BLUE), each of whom plays a finite or infinite collection of sets. Certain requirements are specified in advance. Each player may enumerate into the sets he is playing finitely many elements at every stage. At the end the game is won according to whether the sets satisfy the predetermined requirements or not.