Ordinal recursion

Abstract

We consider a certain method of effectively calculating functions of the positive integers, related to the ‘transfinite recursion’ of Ackermann(1). It arises by use of well-ordered series, and one might hope that the functions so generated could be classified according to the ordinal of the series involved, but we shall see that the use of well-ordered series is not at all essential, and in any case no ordinal other than ω need be used. We investigate how any calculable function (that is, general recursive) can be derived by ordinal recursion (as we name our method), and prove a best possible result.