Vol. 15, No. 3, 1965

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 305: 1
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Vol. 299: 1  2
Vol. 298: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Subscriptions
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
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
Abstract

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
Milestones
Received: 25 January 1964
Published: 1 September 1965
Authors
Robert Wells Ritchie