Misunderstanding the Church-Turing thesis?

Question

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.

My questions:

1. Is my interpretation of the Church-Turing thesis correct?

2. 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?

3. Is hyper computation taken seriously by mainstream computability theorists, or is it the CS equivalent of cold fusion and perpetual motion?

Answer 1

The fields of philosophy and CS apparently have different definitions/interpretations of the thesis. In CS, I believe it is standard/accepted to define the Church-Turing thesis as the article's "Misunderstandings" section's "Thesis M" (under the narrow/worldly view). However, the article claims that this is an incorrect definition of Church-Turing. So we simply disagree. (And let's try to avoid starting an argument with them about it ... pointless arguments are their forte, after all.)

The approach taken by philosophers is unfortunate, as the average layman is probably interested in the CS Church-Turing thesis, not the philosophy one espoused in the article. So they will cite the article while thinking it refers to our practical/reasonable definition, when it doesn't.

So my answers to your specific questions:

1. Yes, as far as I can tell.

2. I'd tell them that the article refers to a highly specialized philosophy-definition of Church-Turing. But regardless of what one calls the "true" Church-Turing thesis, the following thesis is almost universally believed among computer scientists: "Any usable machine of computation that can be built in this universe can be simulated by a Turing Machine".

3. If by hypercomputation you mean physically possible/realizable, then no, it's not taken seriously. But it is interesting to study hypercomputation models even if they cannot appear in the real world, and we do so all the time. For instance, we may consider a Turing Machine that has access to an oracle that solves the halting problem. This object is studied all the time in theory and is uncontroversial, but nobody believes that one can actually be built.

Answer 2

The Stanford Encyclopedia of Philosophy article seems to be missing a very important point. There were no computers when Turing wrote his 1936 paper. I believe he was thinking about them already, but to explain his theories to the mathematician on the street, who had never dreamt of computing machines that had capabilities beyond the relatively limited office machines built by companies like IBM, he had to frame them in terms of an effective procedure carried out by a human.

Gandy's paper "Church's Thesis and Principles for Mechanisms," in The Kleene Symposium (1980) states that the Church-Turing thesis does not apply to machines. It then gives what purports to be a proof of it for a very limited class of machines. Among the things that Gandy claims is that the original Church-Turing thesis did not take parallelism into account.

Gandy's machines don't take into account the possibility of randomness, of non-mechanical physics, of action at a distance, of asynchronicity, of continuous variables, and other things that might be used to build actual physical machines.

So was the original Church-Turing thesis intended by Church or Turing to apply to machines? Andrew Hodges has a paper considering this question, in which he quotes Church's review of Turing's paper:

The author [Turing] proposes as a criterion that an infinite sequence of digits 0 and 1 be “computable” that it shall be possible to devise a computing machine, occupying a finite space and with working parts of finite size, which will write down the sequence to any desired number of terms if allowed to run for a sufficiently long time. As a matter of convenience, certain further restrictions are imposed in the character of the machine, but these are of such a nature as obviously to cause no loss of generality—in particular, a human calculator, provided with pencil and paper and explicit instructions, can be regarded as a kind of Turing machine.

So Church clearly thought the Church-Turing thesis extended to machines.

On the other hand, there seems to have been no effort made by Church or Turing to consider the ramifications of quantum (or other non-elementary) physics on computation, so it was clearly a very limited class of machines they were considering.

Answer 3

The quoted passages are correct. They highlight the distinction between Church-Turing Thesis (an unprovable statement about nature of computation) and existence of a Universal Turing Machine (a mathematical theorem).

The existence of the Universal Turing Machine was a nontrivial fact at the time Turing wrote his paper. Nowadays, it is considered trivial, and in the field of programming Universal Turing Machine is called an interpreter, i.e. a program that can run any other program written in a specific language.

What the quoted passages rightly say is that the existence of interpreters cannot prove Church-Turing Thesis.