In Defense of the Unprovability of the Church-Turing Thesis.
Selmer Bringsjord, Gnanadesigan Naveen Sundar · International journal of unconventional computing · 2010
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.