1965/09/01 by Robert W. Ritchie · 3 citations
Computer Science · #Fuzzy Logic and Control Systems
paper · pdf · doi:10.2140/pjm.1965.15.1027
openalex publication_date 1965/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/21
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 Jn 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 nO, 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: