The object of this paper is to explain a certain type of construction which occurs in priority proofs and illustrate it with two examples due to Lachlan and Harrington. The proofs in the examples are essentially the original proofs; our main contribution is to isolate the common part of these proofs. The key ideas in this common part are due to Lachlan; we include several improvements due to Harrington, Soare, Slaman, and the author.Our notation is fairly standard. If X is (...) an r.e. set, Xs is the finite set of elements enumerated in X before step s. if Ф is a recursive functional, Фs is the approximation to Ф at step s; it only queries the oracle about numbers xi and iless-than-or-equals, slantx; and right-pointing angle bracketx0,...,xk−1right-pointing angle bracket is an increasing function of each of its arguments. Sets are sometimes identified with their characteristic functions. Wj isthe jth r.e. set. Xc is the complement of X. (shrink)

§1. The origins of recursion theory. In dedicating a book to Steve Kleene, I referred to him as the person who made recursion theory into a theory. Recursion theory was begun by Kleene's teacher at Princeton, Alonzo Church, who first defined the class of recursive functions; first maintained that this class was the class of computable functions ; and first used this fact to solve negatively some classical problems on the existence of algorithms. However, it was Kleene who, in his (...) thesis and in his subsequent attempts to convince himself of Church's Thesis, developed a general theory of the behavior of the recursive functions. He continued to develop this theory and extend it to new situations throughout his mathematical career. Indeed, all of the research which he did had a close relationship to recursive functions.Church's Thesis arose in an accidental way. In his investigations of a system of logic which he had invented, Church became interested in a class of functions which he called the λ-definable functions. Initially, Church knew that the successor function and the addition function were λ-definable, but not much else. During 1932, Kleene gradually showed1 that this class of functions was quite extensive; and these results became an important part of his thesis 1935a. (shrink)