In Defense of the Unprovability of the Church-Turing Thesis
Selmer Bringsjord and Naveen Sundar G.
One of us has previously argued that the Church-Turing Thesis (CTT), contra Elliot Mendelson, is not provable, and is — in light of the mind’s ability to effortlessly hypercompute — moreover false. But a new, more serious challenge has appeared on the scene: an attempt by Peter Smith to prove CTT. His reasoning is an ingenious “squeezing argument” that makes crucial use of Kolmogorov-Uspenskii (KU) machines.We analyze Smith’s case, and in light of three objections find it wanting. We end by briefly pointing to our next steps in a thorough evaluation of all published attempts to prove CTT.
Keywords: Church-Turing thesis; Kolmogorov-Uspenskii machines; Effective Computation; Hypercomputation; squeezing arguments