Abstract
We give a novel proof that primitive recursive functions are closed under nested simple recursion. This new presentation is supplied with a detailed proof which can be easily formalized in small fragments of Peano Arithmetic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Beklemishev L.D.: Induction rules, reflection principles, and provably recursive functions. Ann. Pure Appl. Logic 85(3), 193–242 (1997)
Buss S.R.: The witness function method and provably recursive functions of Peano arithmetic. In: Prawitz, D., Skyrms, B., Westerstahl, D. (eds) Logic, Methodology and Philosophy of Science IX, 1991, North-Holland, Amsterdam (1994)
Komara J., Voda P.J.: Theorems of Péter and Parsons in computer programming. In: Gottlob, G., Grandjean, E., Seyr, K. (eds) Proceedings of CSL’98, number 1584 in LNCS, pp. 204–223. Springer, Berlin (1999)
Parsons, C.: On a number-theoretic choice schema and its relation to induction. In: Intuitionism and Proof Theory: Proceedings of the Summer Conference at Buffalo N.Y. 1968, pp. 459–473. North-Holland, Amsterdam (1970)
Péter R.: Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktion. Mathematische Annalen 110, 612–632 (1935)
Péter R.: Recursive Functions. Academic Press, Massachusetts (1967)
Rose H.E.: Subrecursion: Functions and Hierarchies Number 9 in Oxford Logic Guides. Clarendon Press, Oxford (1982)
Sieg W.: Herbrand analyses. Arch. Math. Log. 30, 409–441 (1991)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Komara, J. On nested simple recursion. Arch. Math. Logic 50, 617–624 (2011). https://doi.org/10.1007/s00153-011-0236-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-011-0236-9