Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-16T23:38:06.205Z Has data issue: false hasContentIssue false
  • English
  • Français

Unary primitive recursive functions

Published online by Cambridge University Press:  12 March 2014

Daniel E. Severin
Daniel E. Severin*
Affiliation:
Facultad de Ciencias Exactas, Ingenieria y Agrimensura, Universidad Nacional de Rosario, Rosario. Santa Fe, Argentina, URL: http://www.fceia.unr.edu.ar/~daniel, E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article, we study some new characterizations of primitive recursive functions based on restricted forms of primitive recursion, improving the pioneering work of R. M. Robinson and M. D. Gladstone. We reduce certain recursion schemes (mixed/pure iteration without parameters) and we characterize one-argument primitive recursive functions as the closure under substitution and iteration of certain optimal sets.

Keywords

unaryprimitive recursiverecursion schemereduction
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 4 , December 2008 , pp. 1122 - 1138
Copyright
Copyright © Association for Symbolic Logic 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Axt, Paul, Iteration of relative primitive recursion, Mathematische Annalen, vol. 167 (1966), pp. 53–55.CrossRefGoogle Scholar
[2]Dima, Nelu, Sudan function is universal for the class of primitive recursive functions, Studii şi Cercetӑri Matematice, vol. 33 (1981), pp. 59–67.Google Scholar
[3]Georoieva, Nadejda, Another simplification of the recursion scheme, Archiv für Mathematische Logik, vol. 18 (1976), pp. 1–3.Google Scholar
[4]Georoieva, Nadejda, Classes of one-argument recursive functions, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 22 (1976), pp. 127–130.CrossRefGoogle Scholar
[5]Germano, Giorgio and Mazzanti, Stefano, Primitive iteration and unary functions, Annals of Pure and Applied Logic, vol. 40 (1988), pp. 217–256.CrossRefGoogle Scholar
[6]Gladstone, M. D., A reduction of the recursion scheme, this Journal, vol. 32 (1967), no. 4, pp. 505–508.Google Scholar
[7]Gladstone, M. D., Simplifications of the recursion scheme, this Journal, vol. 36 (1971), no. 4, pp. 653–665.Google Scholar
[8]Goodstein, Reuben L., Recursive number theory: A development of recursive arithmetic in a logic-free equation calculus, 1957.Google Scholar
[9]Grzegorczyk, Andrzej, Some classes of recursive functions, Rozprawy Matematyczne, vol. 4 (1953), pp. 1–44.Google Scholar
[10]Mazzanti, Stefano, Bounded iteration and unary functions, MLQ Mathematical Logic Quarterly, vol. 51 (2005), pp. 89–94.CrossRefGoogle Scholar
[11]Naumović, Jovan, A classification of the one-argument primitive recursive functions, Archiv für Mathematische Logik, vol. 23 (1983), pp. 161–174.CrossRefGoogle Scholar
[12]Ritchie, Robert W., Classes of recursive functions based on Ackermann's function, Pacific Journal of Mathematics, vol. 15 (1965). no. 3, pp. 1027–1044.CrossRefGoogle Scholar
[13]Robinson, Julia, General recursive functions, Proceedings of the American Mathematical Society, vol. 1 (1950), no. 6, pp. 703–718.CrossRefGoogle Scholar
[14]Robinson, Julia, A note on primitive recursive functions, Proceedings of the American Mathematical Society, vol. 6 (1955), no. 4, pp. 667–670.CrossRefGoogle Scholar
[15]Robinson, Raphael M., Primitive recursive functions, Bulletin of the American Mathematical Society, vol. 53 (1947), no. 10, pp. 925–942.CrossRefGoogle Scholar
[16]Robinson, Raphael M., Primitive recursive functions II, Proceedings of the American Mathematical Society, vol. 6 (1955), no. 4, pp. 663–666.CrossRefGoogle Scholar
[17]Szalkai, István, On the algebraic structure of primitive recursive functions, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 31 (1985). pp. 551–556.CrossRefGoogle Scholar