Classes of recursive functions based on Ackermann’s function
Robert W. Ritchie · Pacific Journal of Mathematics · 1965
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 inIn the first section below, we define the functions f n (x f y) (trivial variants of Grzegorczyk's fή{x, y)) which we shall use in place of g n (x, y), and develop various properties of these functions.In the second section, we define and study a sequence & n of classes of one-argument functions.Each 5f n is defined from f n (x, x) and other initial functions by composition and pure iteration as studied by Robinson [7].In the third section, we define j^n (slight modifications of Grzegorczyk's J^n) and establish various properties of these classes including that U ^ is the class of all primitive recursive functions.In the final section we establish the equality of ^l and g 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: