As the Church-Turing thesis is not a [ proper mathematical sentence] we cannot prove it. However, we can collect 3s to increase our confidence in its correctness.
The inductive argument
Every computational model we have seen so far is [ reducible] to Turing's model.
Indeed, the thesis was originally formulated independently by Church and Turing in reference to two different computational models ([Turing_machines] and [Lambda_Calculus] respectively). When they were shown to be [equivilance_relation equivalent] it was massive evidence in favor of both of them.
A non-exhaustive list of models which can be shown to be reducible to Turing machines are:
- [Lambda_calculus]
- [Quantum_computation]
- [Nondeterministic_Turing_machines Non-deterministic_Turing_machines]
- [Register_machines]
- The set of [-recursive_functions]
Lack of counterexamples
Perhaps the strongest argument we have for the CT thesis is that there is not a widely accepted candidate to a counterexample of the thesis. This is unlike the Strong Church Turing thesis, where quantum computation stands as a likely counterexample.
One may wonder whether the computational models which use a source of [ randomness] (such as quantum computation or [-probabilistic_Turing_machines]) are a proper counterexample to the thesis: after all, Turing machines are fully [-deterministic], so they cannot simulate randomness.
To properly explain this issue we have to recall what it means for a quantum computer or a probabilistic Turing machine to compute something: we say that such a device computes a function $~$f$~$ if for every input $~$x$~$ the probability of the device outputting $~$f(x)$~$ is greater or equal to some arbitrary constant greater than $~$1/2$~$. Thus we can compute $~$f$~$ in a classical machine, for there exists always the possibility of simulating every possible outcome of the randomness to deterministically compute the probability distribution of the output, and output as a result the possible outcome with greater probability.
Thus, randomness is reducible to Turing machines, and the CT thesis holds.
Comments
Alexei Andreev
Huh… Not sure I understand this. I have BS in CS, but don't remember running across this. Would love to read more.
Jaime Sevilla Molina
I'll try to cover probabilistic Turing machines in other article once I have time. Thanks for your interest!