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. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.88.6 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |