Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.4204/EPTCS.88.6 | ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE |
Field | DocType | Issue |
Algorithm characterizations,Probabilistic Turing machine,Pointer machine,Universal Turing machine,Computer science,Abstract state machines,Random-access machine,Extended finite-state machine,Algorithm,Theoretical computer science,Turing machine | Journal | 88 |
ISSN | Citations | PageRank |
2075-2180 | 5 | 0.45 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nachum Dershowitz | 1 | 2818 | 473.00 |
| Evgenia Falkovich | 2 | 11 | 1.61 |