As the Church-Turing thesis is not a proper mathematical sentence we cannot prove it. However, we can collect 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 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

• Non-deterministicTuringmachines

• 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.