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