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 there exists a 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 leastto the model proposed by Turing. Thus, we cannot prove it in a mathematical sense, but we can .
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 epistemology, and other fields of knowledge.of the CT thesis for computer science in general, artificial intelligence,
- Strong Church Turing thesis
A strengthening of the Church Turing thesis
- Church-Turing thesis: Evidence for the Church-Turing thesis
Why do we believe in CT thesis?
Mathematics is the study of numbers and other ideal objects that can be described by axioms.