Algorithms: A Quest for Absolute Definitions

What is an algorithm? The interest in this foundational problem is not only theoretical; applications include specification, validation and verification of software and hardware systems. We describe the quest to understand and define the notion of algorithm. We start with the Church-Turing thesis and contrast Church’s and Turing’s approaches, and we finish with some recent investigations.

This publication was also reprinted in the following:

• Reprinted in 2004 World Scientific book, Current Trends in Theoretical Computer Science, pages 283-311
• Reprinted in Church’s Thesis After 70 Years (eds. A. Olszewski et al.), Ontos Verlag, 2006, pages 24-57