[Overview] [Previous] [Next]

Turing's Thesis

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.

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