Higher recursion theory.

*(English)*Zbl 0716.03043
Perspectives in Mathematical Logic. Berlin etc.: Springer-Verlag. xv, 344 p. DM 168.00 (1990).

Many arguments in recursion theory are highly combinatorial and they are based on the huge gap between the finite and the infinite set of natural numbers. One of the original motivations for generalizing recursion theory was that a proper generalization would enable us to see how much of this gap is really used. Higher recursion theory is the branch of recursion theory where both the natural numbers and the family of finite sets are properly generalized. One early attempt to generalize recursion theory was based on hyperarithmetic theory where the analogue of (rec., r.e.) was \((\Delta^ 1_ 1,\Pi^ 1_ 1)\). Though this is a misleading analogy, hyperarithmetic theory is the foundation of higher recursion theory.

Part A of the book contains an extensive introduction to hyperarithmetic theory including measure-theoretic arguments, forcing arguments and a proof of Louveau’s separation theorem. Metarecursion represents the first proper generalization of recursion theory. This is treated in part B. Soon two natural extensions of metarecursion emerged, \(\alpha\)-recursion and computations in normal functionals. \(\alpha\)-recursion is treated in part C of the book. Here the combinatorial strength of the notion of ‘finite’ used in various complex arguments in recursion theory is revealed. Higher type computations are purified in E-recursion which is the subject of part D. Here the motivation is more to investigate a natural concept of computation than to analyze classical proofs. It turns out that the nature of this generalization is quite different from \(\alpha\)-recursion.

The book is very suitable for research students wanting to specialize in higher recursion theory, but is also recommended to others that may be interested in learning more about the subject, though not in all details.

Part A of the book contains an extensive introduction to hyperarithmetic theory including measure-theoretic arguments, forcing arguments and a proof of Louveau’s separation theorem. Metarecursion represents the first proper generalization of recursion theory. This is treated in part B. Soon two natural extensions of metarecursion emerged, \(\alpha\)-recursion and computations in normal functionals. \(\alpha\)-recursion is treated in part C of the book. Here the combinatorial strength of the notion of ‘finite’ used in various complex arguments in recursion theory is revealed. Higher type computations are purified in E-recursion which is the subject of part D. Here the motivation is more to investigate a natural concept of computation than to analyze classical proofs. It turns out that the nature of this generalization is quite different from \(\alpha\)-recursion.

The book is very suitable for research students wanting to specialize in higher recursion theory, but is also recommended to others that may be interested in learning more about the subject, though not in all details.

Reviewer: D.Normann

##### MSC:

03D60 | Computability and recursion theory on ordinals, admissible sets, etc. |

03D65 | Higher-type and set recursion theory |

03-02 | Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations |