Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:research:fi-while [2016/03/23 13:25] apeiron |
en:research:fi-while [2018/02/16 01:25] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | FIXME **The redaction of this article is a work in progress.** | + | ====== Title ====== |
| + | |||
| + | Algorithmic Completeness of Imperative Programming Languages | ||
| ====== Abstract ====== | ====== Abstract ====== | ||
| Line 5: | Line 7: | ||
| 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). | 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 \cite{colson, gcd} for examples related to primitive recursive algorithms). | + | 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 ((Loïc Colson: "About primitive recursive algorithms", Theoretical Computer Science 83 (1991) 57–69)) and ((Yiannis N. Moschovakis: "On Primitive Recursive Algorithms and the Greatest Common Divisor Function", Theoretical Computer Science (2003) ))) 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 \cite{asm}) and a version of Jones' While programs. No special knowledge is assumed, because all relevant material will be explained from scratch. | + | 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 ((Yuri Gurevich: "Sequential Abstract State Machines Capture Sequential Algorithms", ACM Transactions on Computational Logic (2000) ))) and a version of Jones' While programs. No special knowledge is assumed, because all relevant material will be explained from scratch. |
| **Keywords**: Algorithm, ASM, Completeness, Computability, Imperative, Simulation. | **Keywords**: Algorithm, ASM, Completeness, Computability, Imperative, Simulation. | ||