Vol. 15, No. 3, 1965

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
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