https://www.dr-apeiron.net/ 2026-05-05T18:46:11+02:00 https://www.dr-apeiron.net/ https://www.dr-apeiron.net/lib/tpl/writr/images/favicon.ico text/html 2018-02-16T01:25:52+02:00 https://www.dr-apeiron.net/doku.php/en:research:fi-while?rev=1518740752&do=diff Title Algorithmic Completeness of Imperative Programming Languages 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). text/html 2018-02-16T01:25:52+02:00 https://www.dr-apeiron.net/doku.php/en:research:ploopc?rev=1518740752&do=diff Title An Imperative Language Characterizing PTIME Algorithms Abstract Abstract State Machines of Y. Gurevich capture sequential algorithms, so we define the set of PTIME algorithms as the set of ASM programs computed in polynomial time (using timer-step principle). Then, we construct an imperative programming language PLoopC using bounded loop with break, and running with any data structure. Finally, we prove that PLoopC computes exactly PTIME algorithms in lock step (one step of the ASM is s… text/html 2018-02-16T01:25:52+02:00 https://www.dr-apeiron.net/doku.php/en:research:thesis-defense?rev=1518740752&do=diff The academic dissertation Imperative Characterization of Sequential Algorithms in general, primitive recursive or polynomial time Here is [the academic dissertation]. Abstract Calculable functions were formalized by different computation models (recursion, lamb\-da calculus, Turing machines) with the same input-output behavior: this is the Church's Thesis. For example, a one-tape Turing machine can simulate the results computed by a two-tapes machine. However, for the palindrome recognition …