[Overview] [Previous] [Next]

Turing's Thesis and Church's Thesis

I've always used the two terms interchangeably, but your textbook makes a distinction, so here it is.

Turing's thesis. Anything that is computable can be computed by a Turing machine. There does not and cannot exist a machine that can compute things a Turing machine cannot compute.

Church's thesis. All the models of computation yet developed, and all those that may be developed in the future, are equivalent in power. We will not ever find a more powerful model.

Copyright 1996 by David Matuszek
Last modified Apr 18, 1996