What is an Algorithm?

Yuri Gurevich

MSR-TR-2011-116 |

We attempt to put the title problem and the Church-Turing thesis into a proper perspective and to clarify some common misconceptions related to Turing’s analysis of computation. We examine two approaches to the title problem, one well-known among philosophers and another among logicians.