most citedA Formalization and Proof of the Extended Church-Turing Thesis -Extended Abstract-

6 citations · 7 across the 2 of their papers we have counts for

collaborators

2 papers

cs.LO2015★ 1 cited

Cellular Automata are Generic

Nachum Dershowitz, Evgenia Falkovich

Any algorithm (in the sense of Gurevich's abstract-state-machine axiomatization of classical algorithms) operating over any arbitrary unordered domain can be simulated by a dynamic…

cs.LO2012★ 6 cited

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

Nachum Dershowitz, Evgenia Falkovich

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…