The precomputation theories of the first chapter were to a large extent patterned on ordinary recursion theory, ORT. In part B we gave an analysis of “higher recursion theory” through the notion of a finite theory which generalizes ORT by moving up in types over the basic domain.

But there are different ways of extending ORT, e.g. from the integers to all or part of the ordinals. Or ORT can be rephrased as a recursion theory on HF, the hereditarily finite sets, and then be extended to other domains of sets, even to the total universe. Both approaches were followed, and we duly got various notions of ordinal and set recursion, leading to theories of primitive recursive functions, to the rudimentary functions, and to admissibility theory.

We shall not in this book retrace in any detail the line of development from ORT to recursion on ordinals and to the notion of an admissible ordinal The literature on this topic is vast, but the reader would do well to consult one of the classics in the field, the 1967 paper of R. Jensen and C. Karp, Primitive recursive set functions [72]. From this one could go to the recent survey of R. Shore, a-recursion theory [152], and the Short course on admissible recursion theory [156] by S. Simpson, the latter being an advertisement—which we endorse—of a book-length exposition to come.

Pure a-recursion theory was soon transformed into a general theory of admissible structures. A thorough exposition of this field is given by J. Barwise in his book, Admissible Sets and Structures [11].

Remark. The references above are strictly pedagogical and do not imply a history of ordinal recursion theory and admissibility theory in any way—the names of S. Kripke and R. Platek have not even been mentioned.

Barwise and Shore give some historical remarks in their respective introduc-tions. It remains to be seen what Simpson will do with the history of the subject in his book. We shall try to document the sources for those parts of the theory that we discuss. The reader should in particular see Section 5.3.