Computability Theory: An Introduction to Recursion Theory, provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The text includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable way.

Frequent historical information presented throughout More extensive motivation for each of the topics than other texts currently available Connects with topics not included in other textbooks, such as complexity theory

pairs, as illustrated. Clearly, this programming language is simple enough to be simulated by any of the common programming languages if we ignore overflow problems. A loop program is a while program with no while commands; that is, it has only clear, increment, copy, and loop commands. Note the important property: A loop 22 Computability Theory program always halts, no matter what. But it is easy to make a while program that never halts. We say that a k-place partial function f on N is

there exists an effective procedure that, given any natural number, will eventually end by supplying us with the answer. “Yes” if the given number is a member of S and “No” if it is not a member of S. (Initially, we are going to examine computability in the context of the natural numbers. Later, we will see that computability concepts can be readily transferred to the context of strings of letters from a finite alphabet. In that context, we can consider a set S of strings, such as the set of

relation. For example, the set {x | Wx = ∅} is 1 by the above, it is not computable by Rice’s theorem, and hence, it is not 1 . We now extend these ideas and define n and n for each n: Classification 1 1 2 2 3 3 Defining condition ∃x Q(t, x) ∀x Q(t, x) ∃y∀x Q(t, x, y) ∀y∃x Q(t, x, y) ∃z∀y∃x Q(t, x, y, z) ∀z∃y∀x Q(t, x, y, z) where Q is a computable relation. And so forth. (It has been estimated that the human mind cannot grasp the meaning of more than five alternating quantifiers.) We further

true sentences of arithmetic: True = {#τ | τ is a true sentence of arithmetic}. For example, the number #∀x∀y∀z∀n n ≤ 2 or xyz = 0 or not xn + yn = zn belongs to the set True. An indication of the complexity of the set True is given by the following result. Proposition: For any set S that is definable in arithmetic, we have S ≤m True. Proof. Say S is defined in arithmetic by the expression α(x1 ). Thus n ∈ S ⇐⇒ #α(¯n) ∈ True for each number n. Since n → #α(¯n) is a computable function, we

these instructions cannot correctly compute f ; they produce the wrong result at the input k. And because k was arbitrary, we are forced to conclude that no set of instructions can correctly compute f . (This is our first example of a partial function that is not effectively calculable. There are a great many more, as will be seen.) Secondly, we can argue that if we had a decision procedure for H, then we could calculate f . To compute f (x), we first use that decision procedure for H to decide