A Formalization and Proof of the Extended Church-Turing Thesis -Extended Abstract-

Nachum Dershowitz
(Tel Aviv University)
Evgenia Falkovich
(Tel Aviv University)

We prove the Extended Church-Turing Thesis: Every effective algorithm can be efficiently simulated by a Turing machine. This is accomplished by emulating an effective algorithm via an abstract state machine, and simulating such an abstract state machine by a random access machine, representing data as a minimal term graph.

In Elham Kashefi, Jean Krivine and Femke van Raamsdonk: Proceedings 7th International Workshop on Developments of Computational Methods (DCM 2011), Zurich, Switzerland, 3rd July 2011, Electronic Proceedings in Theoretical Computer Science 88, pp. 72–78.
Published: 30th July 2012.

ArXived at: https://dx.doi.org/10.4204/EPTCS.88.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org