Church-Turing thesis

by Jaime Sevilla Molina Jun 15 2016 updated Jul 21 2016

A thesis about computational models

[summary:Every [-effectively_computable] Function is [Turing_machine Turing-computable].]

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 %%note:So 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 [reduction 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.