<p>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 <em>forte</em>, after all.)</p>

<p>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.</p>

<p>So my answers to your specific questions:</p>

<ol>
<li><p>Yes, as far as I can tell.</p></li>
<li><p>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".</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2016-01-10T06:03:20.443Z
Thesis M is due to Gandy. Gandy was Turing's student, and Gandy appears to make a distinction between the Church-Turing thesis and his Thesis M in the paper where he proposes Thesis M. So I wouldn't be too sure they were the same thing.
Peter Shor 
CC BY-SA 3.0
2016-01-08T01:26:30.740Z
2016-01-08T01:26:30.740Z
usul
<p>The Stanford Encyclopedia of Philosophy article seems to be missing a very important point. There <strong><em>were no computers</em></strong> 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. </p>

<p>Gandy's paper "Church's Thesis and Principles for Mechanisms," in <em>The Kleene Symposium</em> (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. </p>

<p>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. </p>

<p>So was the original Church-Turing thesis intended by Church or Turing to apply to machines? Andrew Hodges has a <a href="http://www.turing.org.uk/publications/ct70.pdf" rel="nofollow">paper</a> considering this question, in which he quotes Church's review of Turing's paper:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>So Church clearly thought the Church-Turing thesis extended to machines. </p>

<p>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. </p>

CC BY-SA 3.0
2016-01-10T11:56:54.987Z
As mentioned by Usul, there is also the question of what the CT Thesis is in the minds of researchers today, which may well differ from what is written in historic papers.
Jim Hefferon
CC BY-SA 3.0
2016-01-10T12:52:51.160Z
I am pretty sure there were computers when Turing wrote his paper. It is just they were human.
Denis Pankratov
CC BY-SA 3.0
2016-01-10T17:45:54.057Z
Check section I.8 of Classical Recursion Theory where Odifreddi discusses various theses related to Church's thesis and their relation to models of physics.
Kaveh
CC BY-SA 3.0
2016-01-10T00:39:50.437Z
2016-03-23T18:46:32.957Z
2016-03-23T18:46:32.957Z
Peter Shor 
<p>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).</p>

<p>The existence of the <a href="https://en.wikipedia.org/wiki/Universal_Turing_machine" rel="nofollow">Universal Turing Machine</a> 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 <a href="https://en.wikipedia.org/wiki/Interpreter_(computing)" rel="nofollow">interpreter</a>, i.e. a program that can run any other program written in a specific language.</p>

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

CC BY-SA 3.0
2016-01-08T19:27:44.347Z
I tell my students that modern computers *are* Universal Turing Machines, as long as we're willing to buy more RAM as needed.
Andrej Bauer
CC BY-SA 3.0
2016-01-09T00:44:31.217Z
The universality of the UTM with regards to other TM wasn't the only thing proved. It was also proved that UTM were equivalent to Church's Lamda Calculus and to Godel's general recursive functions. All 3 were formalizations of the concept of an algorithm.
Alexander S King
CC BY-SA 3.0
2016-01-08T16:28:04.637Z
2016-01-08T16:28:04.637Z
Denis Pankratov
<p>My understanding of the Church-Turing thesis is the: </p>

<ul>
<li>It puts a limit on what can be computed by <strong>any</strong> discrete and finite process.</li>
<li>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.</li>
</ul>

<p>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 <em>just</em> a thesis and the there are several proposals for super-Turing computation or hypercomputation. </p>

<p>The mostly frequently cited source for this is the <a href="http://plato.stanford.edu/entries/church-turing/">Stanford Encyclopedia of Philosophy  (SEP) article on the Church-Turing thesis</a>. </p>

<p>In particular the article has a section titled <a href="http://plato.stanford.edu/entries/church-turing/#Bloopers">"Misunderstandings of the thesis"</a>, which states the following: </p>

<blockquote>
  <p>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.</p>
  
  <p>[...] 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.</p>
</blockquote>

<p>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 <a href="http://rationallyspeaking.blogspot.com/2013/08/computation-church-turing-and-all-that.html">Massimo Pigliucci</a>. 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, <a href="https://en.wikipedia.org/wiki/Jack_Copeland">Jack Copeland</a>, is an established philosopher who has published extensively on Turing and on AI. </p>

<p>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. </p>

<p>My questions:</p>

<ol>
<li><p>Is my interpretation of the Church-Turing thesis correct? </p></li>
<li><p>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? </p></li>
<li>Is hyper computation taken seriously by mainstream computability theorists, or is it the CS equivalent of cold fusion and perpetual motion? </li>
</ol>

CC BY-SA 3.0
2016-01-06T19:17:03.200Z
see [What would it mean to disprove Church-Turing thesis?](http://cstheory.stackexchange.com/q/88/)
Kaveh
CC BY-SA 3.0
2016-01-06T19:22:33.747Z
see also [Why has hypercomputation research died down?](http://cstheory.stackexchange.com/q/9555/)
Kaveh
CC BY-SA 3.0
2016-01-10T17:41:22.357Z
See also [section I.8  in Classical Recursion Theory](https://books.google.ca/books?id=ahBLqshTFMwC&pg=PA101) by Odifreddi.
Kaveh
<church-turing-thesis><hypercomputation>
Misunderstanding the Church-Turing thesis?
Alexander S King
# Misunderstanding the Church-Turing thesis?

(Asked by: username_0 on 2016-01-06)

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](http://plato.stanford.edu/entries/church-turing/).

In particular the article has a section titled ["Misunderstandings of the thesis"](http://plato.stanford.edu/entries/church-turing/#Bloopers), 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](http://rationallyspeaking.blogspot.com/2013/08/computation-church-turing-and-all-that.html). 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](https://en.wikipedia.org/wiki/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?

**Tags:** church-turing-thesis, hypercomputation
> **Comments:**
> **username_1**: see [What would it mean to disprove Church-Turing thesis?](http://cstheory.stackexchange.com/q/88/)  
> **username_1**: see also [Why has hypercomputation research died down?](http://cstheory.stackexchange.com/q/9555/)  
> **username_1**: See also [section I.8  in Classical Recursion Theory](https://books.google.ca/books?id=ahBLqshTFMwC&pg=PA101) by Odifreddi.  

---

## 3 answers

### Answer by username_2 on 2016-01-08. Score: 10

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.

> **Comments:**
> **username_3**: Thesis M is due to Gandy. Gandy was Turing's student, and Gandy appears to make a distinction between the Church-Turing thesis and his Thesis M in the paper where he proposes Thesis M. So I wouldn't be too sure they were the same thing.  

---

### Answer by username_3 on 2016-01-10. Score: 7

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](http://www.turing.org.uk/publications/ct70.pdf) 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.

> **Comments:**
> **username_4**: As mentioned by Usul, there is also the question of what the CT Thesis is in the minds of researchers today, which may well differ from what is written in historic papers.  
> **username_5**: I am pretty sure there were computers when Turing wrote his paper. It is just they were human.  
> **username_1**: Check section I.8 of Classical Recursion Theory where Odifreddi discusses various theses related to Church's thesis and their relation to models of physics.  

---

### Answer by username_5 on 2016-01-08. Score: 1

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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Interpreter_(computing)), 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.

> **Comments:**
> **username_6**: I tell my students that modern computers *are* Universal Turing Machines, as long as we're willing to buy more RAM as needed.  
> **username_0**: The universality of the UTM with regards to other TM wasn't the only thing proved. It was also proved that UTM were equivalent to Church's Lamda Calculus and to Godel's general recursive functions. All 3 were formalizations of the concept of an algorithm.  

---

