×

Unary primitive recursive functions. (English) Zbl 1158.03023

In the paper some new characterizations of the set of primitive recursive functions are given. They are based on restricted forms of primitive recursion. This improves the pioneering work of R. M. Robinson and M. D. Gladstone. It is also shown that certain recursion schemes (mixed/pure iteration without parameters) can be reduced. It is proved that the set of unary primitive recursive functions is the closure under substitution and iteration of certain optimal sets.

MSC:

03D20 Recursive functions and relations, subrecursive hierarchies
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] DOI: 10.1002/malq.19760220117 · Zbl 0339.02036 · doi:10.1002/malq.19760220117
[2] A reduction of the recursion scheme 32 pp 505– (1967) · Zbl 0157.01702
[3] Studii şi Cercetri Matematice 33 pp 59– (1981)
[4] DOI: 10.1007/BF01361215 · Zbl 0192.05002 · doi:10.1007/BF01361215
[5] DOI: 10.1002/malq.19850313503 · Zbl 0559.03026 · doi:10.1002/malq.19850313503
[6] DOI: 10.1090/S0002-9939-1955-0073535-4 · doi:10.1090/S0002-9939-1955-0073535-4
[7] DOI: 10.1090/S0002-9904-1947-08911-4 · Zbl 0034.29102 · doi:10.1090/S0002-9904-1947-08911-4
[8] DOI: 10.1090/S0002-9939-1955-0073536-6 · doi:10.1090/S0002-9939-1955-0073536-6
[9] DOI: 10.1090/S0002-9939-1950-0038912-1 · doi:10.1090/S0002-9939-1950-0038912-1
[10] DOI: 10.2140/pjm.1965.15.1027 · Zbl 0133.24903 · doi:10.2140/pjm.1965.15.1027
[11] DOI: 10.1007/BF02023023 · Zbl 0544.03015 · doi:10.1007/BF02023023
[12] Rozprawy Matematyczne 4 pp 1– (1953)
[13] DOI: 10.1002/malq.200410010 · Zbl 1077.03024 · doi:10.1002/malq.200410010
[14] Recursive number theory: A development of recursive arithmetic in a logic-free equation calculus (1957) · Zbl 0077.01401
[15] Simplifications of the recursion scheme 36 pp 653– (1971)
[16] DOI: 10.1016/0168-0072(88)90032-2 · Zbl 0664.68047 · doi:10.1016/0168-0072(88)90032-2
[17] Archiv für Mathematische Logik 18 pp 1– (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.