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.