Affiliations: University of Rouen, Computer Scicence Dept., LITIS, Technopole Madrillet, France. Philippe.Andary, Bruno.Patrou@univ-rouen.fr | Université Paris Est Créteil, LACL, IUT Fontainebleau/Senart, France. pierre.valarcher@u-pec.fr
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
