25 citations · 79 across the 35 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.LO2012★ 8 cited
The Generic Model of Computation
Nachum Dershowitz
Over the past two decades, Yuri Gurevich and his colleagues have formulated axiomatic foundations for the notion of algorithm, be it classical, interactive, or parallel, and formal…
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…