Classical recursion theory (CRT) applies to essentially finite sets of natural numbers. CRT predicates can be defined using the first-order predicate calculus (PC) with quantification over the natural numbers, &ohgr;. CRT was defined in 1963 by Georg Kreisel, who replaced the notion of “finite” with “hyperarithmetic,” &ohgr; by the set I of indices of hyperarithmetic sets, and recursively enumerable (r.e.) by .

A predicate is π¹₁ ( &Sgr;¹₁ ) if it can be expressed in PC with a prefix beginning with a universal (existential) quantifier followed by at most one existential (universal) quantifier. A predicate that is both π¹₁ and &Sgr;¹₁ is said to be &Dgr;¹₁ . Hyperarithmetic sets can be shown to be those defined by &Dgr;¹₁ predicates.

This book considers theories beyond CRT, that is, higher recursion theory (HRT). Since CRT can be defined using hyperarithmetic sets, the first step beyond classical recursion theory is hyperarithmetic (HYP) theory, which is covered in Part A of Sacks’s text. The section ends with analytic notions of measure, density, and separability specialized to HYP sets.

Part B is concerned with metarecursion theory, which “lifts classical recursion theory (CRT) from the natural numbers to the recursive ordinals via definitions in hyperarithmetic terms.” Metarecursion is discussed using Post’s method of informal dynamic means, with which it is easier to understand and devise arguments than with more formal methods.

The theory of &agr;-recursion, which includes admissible sets larger than &ohgr;, is discussed in Part C. In part D, E-recursion is defined. The intent is to make meaningful {e}(x) for every set x, where {e} is the set of defining equations for the eth recursive function. E-recursion also deals with sets larger than &ohgr;. One of the more interesting sections considers “Moschovakis witnesses,” which are infinite paths demonstrating the divergence of partial recursive functions: the “witness” provides a method for tracking the nonterminating attempt to compute a value for {e}(a), if a is a divergent element of x with respect to {e}, and displaying the infinite chain of partial results. The section and the book end with results on ordering recursive sets larger than &ohgr;.

The book is carefully written and edited in textbook style for graduate students as well as interested researchers. Most sections are followed by one to nine exercises, for a total of 219 problems. Some are quite hard, with no hints toward solution. They would, however, provide a good focus for a seminar.

Although the text is self-contained, it would be tough going without a knowledge of the methods, notation, and results of CRT (see Soare [1]). The bibliography is quite thorough, from Post’s 1944 paper on r.e. sets, through Hartley Rogers’s 1967 text [2], to a paper by the author on recursive forcing that has yet to appear. HRT is concerned with infinite sets, but the computational and proof methods are applicable to finite sets as well, especially hyperarithmetic (&Dgr;¹₁) sets which, when substituted for finite sets, make the theory more natural.