Vol. 15, No. 3, 1965

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 298: 1
Vol. 297: 1  2
Vol. 296: 1  2
Vol. 295: 1  2
Vol. 294: 1  2
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
Author Index
To Appear
ISSN: 0030-8730
Other MSP Journals
Classes of recursive functions based on Ackermann’s function

Robert Wells Ritchie

Vol. 15 (1965), No. 3, 1027–1044

Grzegorczyk has defined an increasing sequence of classes n of functions with the properties that 3 is the class of elementary functions of Csillag-Kalmar and ∪ℰn is the class of primitive recursive functions. Further, n+1 properly contains n, if n > 2 then n+1 contains a “universal function” over all one-argument functions in n, and a sequence of functions gn(x,y) in terms of which the n are defined has the property that each gn+1(x,x) (eventually) majorizes all the one-argument functions in n.

The functions gn(x,y) are defined by somewhat artificial nested recursions, and Grzegorczyk poses the following question: “Can the same theorems be proved for classes n as for the classes n?” Here n differs from n only in substituting a more natural function fn(x,y) for each gn(x,y) in the definition of the class. In this paper, we answer his question affirmatively. Indeed, we prove that n = n for all n 0, and further, fn+1(x,x) eventually majorizes all the one-argument functions in n.

Mathematical Subject Classification
Primary: 02.70
Received: 25 January 1964
Published: 1 September 1965
Robert Wells Ritchie