5 found
  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 (11 more)  
    Export citation  
    Bookmark   18 citations  
  2.  49
    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 (6 more)  
    Export citation  
    Bookmark   9 citations  
  3.  1
    Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday.Arnon Avron & Nachum Dershowitz (eds.) - 2008 - Springer.
    The Person 1 Boris Abramovich Trakhtenbrot – his Hebrew given name is Boaz – is universally admired as a founding - ther and long-standing pillar of the discipline of computer science. He is the?eld's preeminent distinguished researcher and a most illustrious trailblazer and disseminator. He is unmatched in combining farsighted vision, unfaltering c- mitment, masterful command of the?eld, technical virtuosity, æsthetic expr- sion, eloquent clarity, and creative vigor with humility and devotion to students and colleagues. For over half a century, (...)
    No categories
    Direct download  
    Export citation  
  4. Synthetic Programming.Nachum Dershowitz - 1985 - Artificial Intelligence 25 (3):323-373.
    Direct download (2 more)  
    Export citation  
  5.  12
    On the Parallel Computation Thesis.Nachum Dershowitz & Evgenia Falkovich-Derzhavetz - 2016 - Logic Journal of the IGPL 24 (3):346-374.