×

Primitive recursion in the abstract. (English) Zbl 1435.68064

Summary: Recurrence can be used as a function definition schema for any nontrivial free algebra, yielding the same computational complexity in all cases. We show that primitive-recursive computing is in fact independent of free algebras altogether, and can be characterized by a generic programming principle, namely the control of iteration by the depletion of finite components of the underlying structure.

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
03C13 Model theory of finite structures
03D75 Abstract and axiomatic computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andary, P., Patrou, B. and Valarcher, P. (2005). About implementation of primitive recursive algorithms. In: Beauquier, D., Börger, E. and Slissenko, A. (eds.) Proceedings of the 12th International Workshop on Abstract State Machines, 77-90. · Zbl 1252.68114
[2] Andary, P., Patrou, B. and Valarcher, P. (2011). A representation theorem for primitive recursive algorithms. Fundamenta Informaticae107 (4) 313-330. · Zbl 1252.68114
[3] Blum, L., Shub, M. and Smale, S. (1989). On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society211-46. · Zbl 0681.03020
[4] Börger, E. (2002). The origins and the development of the ASM method for high level system design and analysis. Journal of UCS8 (1) 2-74.
[5] Bournez, O., Cucker, F., De Naurois, P. J. and Marion, J.-Y. (2003). Computability over an arbitrary structure. Sequential and parallel polynomial time. In: Foundations of Software Science and Computational Structures, 185-199. · Zbl 1029.68056
[6] Dijkstra, E. W. (1976). A Discipline of Programming. Prentice-Hall. · Zbl 0368.68005
[7] Ebbinghaus, H.-D. and Flum, J. (1995). Finite Model Theory. Springer-Verlag. · Zbl 0841.03014
[8] Grädel, E. and Gurevich, Y. (1995). Metafinite model theory. In: Leivant, D. (ed.) Logic and Computational Complexity, Lecture Notes in Computer Science, vol. 960, Springer, 313-366. · Zbl 0892.68033
[9] Gries, D. (1981). The Science of Programming, Texts and Monographs in Computer Science. Springer. · Zbl 0472.68003
[10] Gurevich, Y. (1988). Logic in computer science column. Bulletin of the EATCS3571-81.
[11] Gurevich, Y. (1993). Evolving algebras: An attempt to discover semantics. In: Rozenberg, G. and Salomaa, A. (eds.) Current Trends in Theoretical Computer Science, vol. 40, World Scientific, 266-292.
[12] Gurevich, Y. (2001). The sequential ASM thesis. In: Current Trends in Theoretical Computer Science, World Scientific, 363-392. · Zbl 1049.68155
[13] Hartmanis, J. (1972). On non-determinancy in simple computing devices. Acta Informatica1336-344. · Zbl 0229.68014
[14] Van Heijenoort, J. (1967). From Frege to Gödel, A Source Book in Mathematical Logic, 1879-1931. Harvard University Press. · Zbl 0183.00601
[15] Kleene, S. C. (1969). Formalized Recursive Functionals and Formalized Realizability. Memoirs of the AMS. American Mathematical Society. · Zbl 0184.02004
[16] Leivant, D. (2018). A theory of finite structures. CoRR, abs/1808.04949.
[17] Peter, R. (1951). Rekursive Funktionen. Akadémia Kiadó.
[18] Sazonov, V. Y. (1980). Polynomial computability and recursivity in finite domains. Elektronische Informationsverarbeitung und Kybernetik16 (7) 319-323. · Zbl 0455.03018
[19] Skolem, T. (1923). Einige bemerkungen zur axiomatischen begründung der mengenlehre. In Matematikerkongressen in Helsingfors Den femte skandinaviske matematikerkongressen, 1922 Heijenoort (1967), 217-232. English translation in (Heijenoort, 1967). · JFM 49.0138.02
[20] Strahm, T. and Zucker, J. I. (2008). Primitive recursive selection functions for existential assertions over abstract algebras. Journal of Logical and Algebraic Methods76 (2) 175-197. · Zbl 1156.03043
[21] Winskel, G. (1993). The Formal Semantics of Programming Languages: An Introduction. MIT Press. · Zbl 0919.68082
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.