Affiliations: Université Paris-Est Créteil (UPEC), Laboratoire d’Algorithmique, Complexité et Logique (LACL), IUT Sénart-Fontainebleau, France. [email protected]
Correspondence:
[†]
Address for correspondence: Université Paris-Est Créteil (UPEC), Laboratoire d’Algorithmique, Complexité et Logique (LACL), IUT Sénart-Fontainebleau, France.
Note: [*] This work is partially supported by the french program ANR 12 BS02 007 01.
Abstract: According to the Church-Turing Thesis, effectively calculable functions are functions computable by a Turing machine. Models that compute these functions are called Turing-complete. For example, we know that common imperative languages (such as C, Ada or Python) are Turing complete (up to unbounded memory). Algorithmic completeness is a stronger notion than Turing-completeness. It focuses not only on the input-output behavior of the computation but more importantly on the step-by-step behavior. Moreover, the issue is not limited to partial recursive functions, it applies to any set of functions. A model could compute all the desired functions, but some algorithms (ways to compute these functions) could be missing (see [10, 27] for examples related to primitive recursive algorithms). This paper’s purpose is to prove that common imperative languages are not only Turing-complete but also algorithmically complete, by using the axiomatic definition of the Gurevich’s Thesis and a fair bisimulation between the Abstract State Machines of Gurevich (defined in [16]) and a version of Jones’ While programs. No special knowledge is assumed, because all relevant material will be explained from scratch.
