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
    0 references

    Identifiers