Alan Turing defined Turing machines in an attempt to formalize the notion of an *effective
procedure* (essentially the same as what we would call an "algorithm").

At approximately the same time, other mathematicians were independently working on the same problem.

- Alonzo Church -- Lambda calculus
- Emil Post -- Production systems
- Raymond Smullyan -- Formal systems
- Stephen Kleene -- Recursive function theory
- Noam Chomsky -- Unrestricted grammars

All of these formalisms were proved equivalent to one another. This led to

**Turing's Thesis (weak form):** A Turing machine can compute anything that can be
computed by a general-purpose digital computer.

**Turing's Thesis (strong form):** A Turing machine can compute anything that can be
computed.

The strong form of Turing's thesis cannot be "proved," because it states a relationship between mathematical concepts and the "real world."

Copyright © 1996 by David Matuszek

Last modified Apr 7, 1996