1. A Natural Axiomatization of Computability and Proof of Church's Thesis.Nachum Dershowitz & Yuri Gurevich - 2008 - Bulletin of Symbolic Logic 14 (3):299-350.
    Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's (...)
    Direct download (12 more)  
    Export citation  
    Bookmark   6 citations  
  2.  29
    When Are Two Algorithms the Same?Andreas Blass, Nachum Dershowitz & Yuri Gurevich - 2009 - Bulletin of Symbolic Logic 15 (2):145-168.
    People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.
    Direct download (5 more)  
    Export citation  
    Bookmark   2 citations  
  3.  2
    On the Parallel Computation Thesis.Nachum Dershowitz & Evgenia Falkovich-Derzhavetz - 2016 - Logic Journal of the IGPL 24 (3):346-374.