Super-exponentials nonprimitive recursive, but rudimentary
type: Item
instance of: scholarly article
title: Super-exponentials nonprimitive recursive, but rudimentary
zbMATH Open document ID: 0632.03036
DOI: 10.1016/0020-0190(87)90205-5
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: \textit{J. H. Bennett} [``On spectra'', Ph. D. Dissertation, Princeton (1962)] proved that \(x^ y\) is rudimentary in \textit{R. M. Smullyan}'s sense [Theory of formal systems (1961; Zbl 0097.245); see \textit{P. Pudlak}, Commentat. Math. Univ. Carol. 24, 667-671 (1983; Zbl 0533.03032) for a short proof]. \textit{S. Finkelstein} (1977) [quoted following \textit{K. Harrow}, Inf. Control 36, 102-117 (1978; Zbl 0374.02019)] and \textit{A. V. Proskurin} [Zap. Nauchn. Semin. Leningr. Otd. Math. Inst. Steklova 88, 186-191 (1979; Zbl 0429.03023)] have proved that each primitive recursive section of Ackermann's function is rudimentary. In this paper we extend their result by showing that every non-primitive recursive super- exponential of Ackermann's type is rudimentary.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 4027450
zbMATH Keywords: nonprimitive recursive function
zbMATH Keywords: rudimentary function
zbMATH Keywords: loop-program
zbMATH Keywords: Ackermann's function
Wikidata QID: Q57001803
author: Cristian S. Calude
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90205-5
OpenAlex ID: W2071613174
cites work: Loop-programs and polynomially computable functions
cites work: A syntactical definition of the problem
cites work: Expectations for Inbreeding Depression on Self-Fertilization of Tetraploids
cites work: Q3026989
cites work: Q5824357
cites work: Equivalence of some Hierarchies of Primitive Recursive Functions
cites work: Rudimentary interpretation of two-tape turing computation
cites work: Q5628106
cites work: Q3241197
cites work: Q3902991
cites work: Q3315507
cites work: Q5537599
cites work: Q3914460
cites work: Q5635418
cites work: Monadic Elementary Formal Systems
cites work: Q3723717
DBLP publication ID: journals/ipl/Calude87
description: scientific article; zbMATH DE number 4027450