Did you mean: Dimwits, Nahum
  1. Andreas Blass, Nachum Dershowitz & Yuri Gurevich (2009). When Are Two Algorithms the Same? 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)  
     
    My bibliography  
     
    Export citation  
  2. Nachum Dershowitz & Yuri Gurevich (2008). A Natural Axiomatization of Computability and Proof of Church's Thesis. 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 (8 more)  
     
    My bibliography  
     
    Export citation