My understanding of the Church-Turing thesis is the:
- It puts a limit on what can be computed by any discrete and finite process.
- Although still a thesis, not a theorem, if it were to be disproven, this wouldn't mean just an update to our current models of computation. It would be a paradigm shifting result for mathematics and physics in general.
Yet many discussions on the Philosophy SE (where I usually hang out) turn to the possibility of "Super-Turing" computation, and arguments in philosophy of mind question are frequently hinged on the proposition that Church-Turing is just a thesis and the there are several proposals for super-Turing computation or hypercomputation.
The mostly frequently cited source for this is the Stanford Encyclopedia of Philosophy (SEP) article on the Church-Turing thesis.
In particular the article has a section titled "Misunderstandings of the thesis", which states the following:
A myth seems to have arisen concerning Turing's paper of 1936, namely that he there gave a treatment of the limits of mechanism and established a fundamental result to the effect that the universal Turing machine can simulate the behaviour of any machine. The myth has passed into the philosophy of mind, generally to pernicious effect.
[...] Turing did not show that his machines can solve any problem that can be solved "by instructions, explicitly stated rules, or procedures", nor did he prove that the universal Turing machine "can compute any function that any computer, with any architecture, can compute". He proved that his universal machine can compute any function that any Turing machine can compute; and he put forward, and advanced philosophical arguments in support of, the thesis here called Turing's thesis. But a thesis concerning the extent of effective methods -- which is to say, concerning the extent of procedures of a certain sort that a human being unaided by machinery is capable of carrying out -- carries no implication concerning the extent of the procedures that machines are capable of carrying out, even machines acting in accordance with ‘explicitly stated rules’. For among a machine's repertoire of atomic operations there may be those that no human being unaided by machinery can perform.
The above mentioned section and especially the quoted passages seem blatantly wrong to me, as if the author doesn't even get the concept of a Turing machine or what the Church-Turing thesis is. And yet, the article is constantly cited as a source by those who argue against the Church-Turing thesis, not just in the Philosophy SE, but even by relatively well known philosophers like Massimo Pigliucci. The main reasons why the article carries so much weight is that the SEP is considered a reputable source in the philosophy community, and the articles there are subject to review, and that the article's author, Jack Copeland, is an established philosopher who has published extensively on Turing and on AI.
And yet the way I see it, the article is fundamentally wrong in its presentation of the thesis, reputability of the source and the author not withstanding.
Is my interpretation of the Church-Turing thesis correct?
How could one refute those who use that article's "Misunderstandings" section as a justification for the idea that computing beyond the Turing limit is a realistic prospect?
- Is hyper computation taken seriously by mainstream computability theorists, or is it the CS equivalent of cold fusion and perpetual motion?