Classes of recursive functions based on Ackermann’s function

Abstract

Grzegorczyk has defined an increasing sequence of classes g^ of functions with the properties that gf 3 is the class of elementary functions of Csillag-Kalmar and Ugf 71 is the class of primitive recursive functions. Further, g^+ properly contains gf n , if n>2 then g^+ 1 contains a "universal function" over all one-argument functions in gf w , and a sequence of functions g n (%, V) in terms of which the ^n are defined has the property that each g n +i(%, %) (eventually) majorizes all the one-argument functions in g 771 . The functions g n {%, y) are defined by somewhat artificial nested recursions, and Grzegorczyk poses the following question: "Can the same theorems be proved for classes J^n as for the classes g" w V Here ^n differs from c n only in substituting a more natural function fj(%, y) for each g n (x, y) in the definition of the class. In this paper, we answer his question affirmatively. Indeed, we prove that ^n=-c n for all n^O, and further, f+i(x f x) eventually majorizes all the one-argument functions in 7 *, and then discuss Grzegorczyk's f(x,y) and prove that ^~n also equals gf\ 1* The functions f n (x, y). In [1], Ackermann defines a function of three variables which he shows is not primitive recursive. He obtains this function by considering the functions x + y, xy and x v , observing that each is obtained from the preceding by a recursive definition and generalizing this process. Let us depart slightly from [1] and generalize the sequence of three functions as follows: