Theory of AlgoRithms : Machines, completeness, Axiomatization and physical Constraints. – TARMAC

A huge amount of algorithms have been designed and presented using different frameworks. But the question "what is an algorithm?" remained unsettled until the end of the twentieth century.

The solution came only recently, as a result of a combination of three successive approaches to our intuitive notion.

The first approach is historically called "denotational".

By denotational approach, we mean the study of input/output behavior of the algorithm (considered as a black box): which function or relation does it compute?
Turing machines formalized this approach. Other models were then constructed and proved to define the same class of computable functions. They lead to the so-called Church-Turing thesis in 1936. However, these models now called Turing-complete or "denotationally"-complete usually have behaviors (ways to compute the functions), which are quite different. Hence, for Turing-complete models classes of implementable algorithms associated with these models are usually distinct. And in fact, no known model before 1984 does compute all algorithms. Let us insist the Church-Turing thesis is not about algorithms but about what they compute.

Which brings us to the second approach called "operational".
By operational we mean the study of the execution of the algorithm, how does it work? What is its step-by-step behavior and how evolves its environment? A model of computation, which captures the behavior of all algorithms, is called “operationally” complete. Such a compelling model, that of the Abstract State Machine (ASM), was exhibited by Yuri Gurevich {Gur-84, Gur-85}, which led to the sequential thesis {Gur-00} and later to Blass-Gurevich parallel thesis {BG-03 BG-08}. These two theses are the analog of the Church-Turing thesis but for the notion of algorithm instead of computability. They assert that the execution of any sequential algorithm (resp. parallel) can be emulated step for step by the execution of a sequential (resp. parallel) ASM. Our goal is not to further justify the thesis of Gurevich based on some mathematical principles (this has already been extensively done since 1984).

And finally the last approach is based on axiomatic presentation.
By axiomatic approach we consider the approach originally developed by R. Gandy in {Ga-80} and followed by W. Sieg {Sie-08}. Gandy intended to complement Turing’s analysis of human computers with an analysis of computation by mechanical devices. He gives a finite set of axioms for “machine computation”: discrete, deterministic action that is limited to "local causation" by the speed of light. However, Gandy’s axioms are rather for defining computational (by machines) functions than for defining algorithms. In {Gur-84, Gur-85}, the author gives three axioms for defining algorithms.

We pursue three aims: the identification of alternative algorithmically-complete models of computation, that of algorithmically complete programming languages, and justification of these through arguments based on laws of physics.