A Representation Theorem for Primitive Recursive Algorithms

Article type: Research Article

Authors: Andary, Philippe | Patrou, Bruno | Valarcher, Pierre

Affiliations: University of Rouen, Computer Scicence Dept., LITIS, Technopole Madrillet, France. Philippe.Andary, [email protected] | Université Paris Est Créteil, LACL, IUT Fontainebleau/Senart, France. [email protected]

Note: [] Address for correspondence: University of Rouen, Computer Scicence Dept., LITIS, Technopole Madrillet, F-76800 Saint Etienne du Rouvray, Rouen, France

Abstract: We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions) by which it is possible to implement any one of the previously defined algorithms for the PR functions in such a way that their complexity is preserved.

Keywords: primitive recursion, algorithms, abstract state machines, structural complexity

DOI: 10.3233/FI-2011-405

Journal: Fundamenta Informaticae, vol. 107, no. 4, pp. 313-330, 2011