Foundations of Computability

Comparing models of computation

• Udi Boker and Nachum Dershowitz, Oct. 2006, “Comparing Computational Power”, Logic Journal of the IGPL, vol. 14, no. 5, pp. 633-648.
• Udi Boker and Nachum Dershowitz, Oct. 2009, “The Influence of the Domain Interpretation on Computational Models”, Applied Mathematics and Computation, vol. 215, no. 4, pp. 1323-1339.
• Udi Boker and Nachum Dershowitz, July 2006, “A Hypercomputational Alien”, J. of Applied Mathematics & Computation, vol. 178, no. 1, pp. 44-57; available online 9 Nov. 2005.
• Nachum Dershowitz, December 2005, “The Four Sons of Penrose”, Proceedings of the Eleventh Conference on Logic Programming for Artificial Intelligence and Reasoning (LPAR), Jamaica, G. Sutcliffe and A. Voronkov, eds., Lecture Notes in Computer Science, vol. 3835, Springer-Verlag, Berlin, pp. 125-138.
  

Honest representations

• Udi Boker and Nachum Dershowitz, 2015, “Honest Computability and Complexity”, in Martin Davis Jubilee Volume, Alberto Policriti and Eugenio Omodeo, eds., Outstanding Contributions to Logic Series, Springer.
• Nachum Dershowitz and Evgenia Falkovich, July 2012, “Honest Universality”, S. Abramsky, ed., Special issue of the Philosophical Transactions of the Royal Society A, vol. 370, no. 1971, pp. 3340-3348.
  

Generic models of computation

• Nachum Dershowitz, July 2011, “The Generic Model of Computation”, Proceedings of the Seventh International Workshop on Developments in Computational Models (DCM 2011), Elham Kashefi, Jean Krivine, and Femke van Raamsdonk, eds., Zurich, Switzerland, Electronic Proceedings Theoretical Computer Science (EPTCS), vol. 88, pp. 59-71. Published July 2012.
  
• Andreas Blass, Nachum Dershowitz, and Yuri Gurevich, Aug. 2010, “Exact Exploration and Hanging Algorithms”, Proceedings of the 24th International Workshop on Computer Science Logic (CSL 2010), Anuj Dawar and Helmut Veith, eds., Brno, Czech Republic, Lecture Notes in Computer Science, vol. 6247, Springer-Verlag, Berlin, pp. 140-154.
• Nachum Dershowitz, September 2013, “Res Publica: The Universal Model of Computation”, Proceedings of the 22nd EACSL Conference on Computer Science Logic (CSL), Torino, Italy, pp. 5-10.
  
• Nachum Dershowitz and Evgenia Falkovich, April 2015, “Cellular Automata are Generic”,  Electronic Proceedings Theoretical Computer Science (EPTCS), vol. 179, pp. 17-32.
  
• Olivier Bournez, Nachum Dershowitz, and Evgenia Falkovich, May 2012, “Towards an Axiomatization of Simple Analog Algorithms”, Proceedings of the Conference on the Theory and Applications of Models of Computation (TAMC), Manindra Agrawal, S. Barry Cooper, and Angsheng Li, eds., Beijing, China, Lecture Notes in Computer Science, vol. 7287, pp. 525-536.
  

The Church-Turing thesis

• Nachum Dershowitz and Yuri Gurevich, Sept. 2008, “A Natural Axiomatization of Computability and Proof of Church’s Thesis”, Bulletin of Symbolic Logic, vol. 14, no. 3, pp. 299-350.
• Udi Boker and Nachum Dershowitz, 2008, “The Church-Turing Thesis over Arbitrary Domains”, Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, Arnon Avron, Nachum Dershowitz, and Alexander Rabinovich, eds., Lecture Notes in Computer Science, vol. 4800, Springer-Verlag, Berlin, pp. 199-229.
• Udi Boker and Nachum Dershowitz, Aug. 2010, “Three Paths to Effectiveness”, Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday, Andreas Blass, Nachum Dershowitz, and Wolfgang Reisig, eds., Lecture Notes in Computer Science, vol. 6300, Springer-Verlag, Berlin, pp. 135-146.
• Nachum Dershowitz and Evgenia Falkovich, 2012, “Effectiveness”, Hector Zenil, ed., Computation in Nature & The Nature of Computation, World Scientific/Imperial College Press.
• Nachum Dershowitz and Evgenia Falkovich, February 2012, “The Invariance Thesis”.
• Nachum Dershowitz and Evgenia Falkovich, 2015, “On the Parallel Computation Thesis”.