Church-Turing thesis

The Church-Turing thesis (often abbreviated CT thesis) states:

Every effectively computable function is Turing-computable

That is, for every function which can be computed by physical means noteSo no hypercomputers there exists a Turing machine which computes exactly that.

The Church-Turing thesis is not a definite mathematical statement, but an inductive statement which affirms that every sensible model of computation we can come up with is equivalent or at least reducible to the model proposed by Turing. Thus, we cannot prove it in a mathematical sense, but we can gather evidence for it.

For example, this model was proven to coincide with Church’s lambda calculus, another universal model of computation, and the equivalence between Church’s lambda calculus and Turing’s automatic machines is often taken as evidence that they correctly capture our intuition of “effectively computable”.

There are many consequences of the CT thesis for computer science in general, artificial intelligence, epistemology, and other fields of knowledge.