Super-exponentials nonprimitive recursive, but rudimentary (Q1095134)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Super-exponentials nonprimitive recursive, but rudimentary |
scientific article |
Statements
Super-exponentials nonprimitive recursive, but rudimentary (English)
0 references
1987
0 references
\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.
0 references
nonprimitive recursive function
0 references
rudimentary function
0 references
loop-program
0 references
Ackermann's function
0 references