Church-Turing thesis: Evidence for the Church-Turing thesis

https://arbital.com/p/evidence_for_CT_thesis

by Jaime Sevilla Molina Jun 17 2016 updated Jun 20 2016

Why do we believe in CT thesis?


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:

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

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

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!