Church-Turing thesis: Evidence for the Church-Turing thesis
The inductive argument
Every computational model we have seen so far isto Turing’s model.
Indeed, the thesis was originally formulated independently by Church and Turing in reference to two different computational models (and respectively). When they were shown to be 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:
The set of
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(such as quantum computation or ) are a proper counterexample to the thesis: after all, Turing machines are fully , 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.
- Church-Turing thesis
A thesis about computational models