2
$\begingroup$

Church-Turing thesis : Every effectively calculable function is a TM-computable function.

But, hypercomputation models are strictly more powerful than TM and can solve TM-uncomputable problems on the paper.

Does this imply that, for one who believes in the Church-Turing thesis, there is only two options :

  1. There is two distincts worlds : The effective one (where Church-Turing thesis applies) and the paper one (where Church-Turing thesis doesn't apply necessarily). That is the physical world and the ideas world of the classical dualism theory.
  2. All the hypercomputation models are inconsistent. Using an hyper-TM in a reasoning is the same than, for instance, using an integer both even and odd in a reasoning, this can lead to false conclusions.

?

$\endgroup$
  • 1
    $\begingroup$ I dont know much about this work (maybe some people here will care to elaborate), but Yuri Gurevich has done some work regarding the Church-Turing thesis. He claims (i think...) that Turing Machines are not the right interpretation for what we call algorithms, and defines the abstract state machine (where states are models?), relative to which you can actually prove the thesis (something like: abstract state machines are the right way to describe effective computation, and TM's can simulate them). Maybe you should look at research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf $\endgroup$ – Ariel Sep 29 '15 at 16:22
  • 1
    $\begingroup$ What do you mean by "we can proof false assuming that a hyper-TM exists, even theoretically" (emphasis mine)? Prove false under what axioms, with what proof system? Computability theorists assume the existence of Turing machines with oracles for uncomputable problems all the time; I'm not aware of any evidence that such an assumption leads to inconsistent theories. $\endgroup$ – David Richerby Sep 29 '15 at 21:54
  • $\begingroup$ @DavidRicherby By inconsistent theory, I mean : using an hyper-TM in a reasoning is the same than using an integer both even and odd in a reasoning, this can lead to false conclusion (with your favorite axioms/proof system to speak about integers). $\endgroup$ – François Sep 30 '15 at 6:15
  • 2
    $\begingroup$ Jeeze, what's up with the hypercomputation-mumble-jumble these days? $\endgroup$ – Pål GD Sep 30 '15 at 8:01
6
$\begingroup$

There's another possibility: hypercomputation is not implementable in the real world, and is only an imaginary/theoretical concept. If this is the case, then there is no contradiction with the Church-Turing thesis.

Of course, anyone can invent imaginary worlds where strange things are true. For instance, there's the computer scientist's Superman: not only can he leap tall buildings in a single bound, he can also solve undecidable problems in his head! I suppose one could imagine such a thing, but that doesn't mean it has any correspondence to the real world, and the possibility of imagining such a Superman doesn't contradict the Church-Turing thesis. The study of hypercomputation can be thought of as asking, well, ok, so Superman might not be real, but what if he were?

The Church-Turing thesis is a hypothesis about the real world, so imaginary schemes that can't be implemented in the real world don't contradict it.

$\endgroup$
  • $\begingroup$ Indeed, this is already my point 1 : imaginary worlds are not part of the real world if you can implement hyperTM inside (since you can not in the real world). So, there is two kinds of worlds : imaginary ones and physical one. Instead of this, I consider in my point 2 that imaginary worlds are from our mind and, since our brain is physical, that imaginary worlds are part of the physical world. Then the Church Turing thesis is also about the imaginary worlds. $\endgroup$ – François Sep 30 '15 at 8:50
  • $\begingroup$ You cannot even implement a Turing Machine in the real world, because there is not enough matter for the infinite tape... $\endgroup$ – Peter Leupold Dec 1 '17 at 16:32
4
$\begingroup$

No, you are confused.

Turing machines and Hypercomputation are both mathematical models, and they are both consistent because we can build mathematical models in which all functions are Turing computable, as well as models in which hypercomputable functions exist. These are of course different models. There is no mystery about having a lot of mathematical models of various theories, for instance, there are models of both euclidean and non-euclidean geometry.

The mathematical theory of computation should not be confused with "the real world". This is a bad thing to do because Turing machines are a piece of mathematics. Do you also think that infinite straight thin lines really exist in the physical world? Or maybe that they are slightly bent because of gravity?

Church's thesis is a piece of premathematical or philosophycal analysis which essentially says "Turing's mathematical definition of computation correctly models what can actually be computed in the real world". This is not a mathematical statement.

In one of the comments you made the following faulty line of reasoning: "... that imaginary worlds are from our mind and, since our brain is physical, that imaginary worlds are part of the physical world." To see why this makes no sense, consider a similar line of reasoning: "Yesterday I imagined a fairy with golden wings, and since the fairy was in my mind, and my brain is physical, the fairy is part of the physical world". The problem is that you are confusing the thoughts in your mind with their physical representation (the electro-chemical functioning of your brain).

A Belgian artist put it very eloquently:

enter image description here

$\endgroup$
  • $\begingroup$ No, I am not confused. Materialism (en.wikipedia.org/wiki/Materialism) assumes that the fairy with golden wings exists in the physical (and only) world : it's an electro-chemical signal. Magritte would still be right : this is not a pipe, it's a physical picture of a pipe with its caption. $\endgroup$ – François Sep 30 '15 at 12:53
  • 1
    $\begingroup$ With all due respect, an electro-chemical signal is not a fairy with golden wings, as my 10 year old daughter, a renowned fairy expert (she knows seven seasons of Winx Club by heart) can readily confirm. $\endgroup$ – Andrej Bauer Sep 30 '15 at 13:05
  • $\begingroup$ And a castle is not a pack of atoms, as my 9 years old brother, a renowned fairy expert, can readily confirm. $\endgroup$ – François Sep 30 '15 at 13:13
  • 1
    $\begingroup$ Are you trying to arrange a marriage here? $\endgroup$ – Andrej Bauer Sep 30 '15 at 13:46
  • $\begingroup$ x) I found this : en.wikipedia.org/wiki/Supervenience $\endgroup$ – François Sep 30 '15 at 16:16
4
$\begingroup$

The Church–Turing thesis only purports to describe the types of processes that qualify as “computational”. It does not assert that “hypercomputational” processes are mathematically inconsistent. Most widely accepted formalizations of mathematics do allow us to define and reason about noncomputable functions.

Some take “computation” to mean “process that can be performed on a Turing machine”. In that view, the Church-Turing thesis is just a definition of the word “computation”, and does not really claim anything.

Some take “computation” to mean “process that matches our intuitive understanding of an algorithm”. In that view, the Church-Turing thesis is just an encoding of our intuition, and its only claims are about what our intuition says.

Some take “computation” to mean “process that can be performed in the real world”. In that view, the Church–Turing thesis becomes a much stronger assertion, but it’s an assertion about physics, not about computer science. It asserts that we cannot build a device capable of hypercomputation within our physical universe. There’s still no reason to think that such a device would be inconsistent with itself mathematically.

(In fact, it’s not even obvious whether such a device would be inconsistent with known theoretical physics—see Malament–Hogarth spacetime. And there’s still a lot about physics that we don’t know. It’s possible that new physics could establish that the universe itself has a Turing-computable model, in which case the Church–Turing thesis would be true. It’s just as possible that some new phenomenon allows us perform real hypercomputation and the Church–Turing thesis would be false.)

$\endgroup$
  • $\begingroup$ "The Church–Turing thesis [...] asserts that we cannot build a device capable of hypercomputation within our physical universe." No it doesn't. The idea of a so-called "physical Church-Turing thesis" is, as I understand it, a much later concept, not due to Church or Turing. Church-Turing merely states that Turing machines correspond to our intuitive idea of algorithm; it says nothing about whether problems might be soluble by physical devices that don't correspond to our intuitive notion of algorithm. $\endgroup$ – David Richerby Sep 29 '15 at 21:41
  • 2
    $\begingroup$ Our intuitive notion of algorithm comes from the physical world. If we found hypercomputation in the physical world, then within a few decades, our intuitive notion of algorithm would surely be adjusted to include this. So, while the physical formulation of the Church–Turing thesis may have been stated later, I think it’s the only reasonable way to interpret the original thesis. $\endgroup$ – Anders Kaseorg Sep 29 '15 at 21:44
  • $\begingroup$ No, not to some intuitive notion of algorithm that we might have at some point in the future: to the intuitive notion of algorithm that we have today. Allow me to rephrase: "Church-Turing merely states that Turing machines correspond to the intuitive idea of algorithm during the 1930s/40s when Church and Turing were thinking about such things which, by the way, is the same idea of algorithm that we have today." $\endgroup$ – David Richerby Sep 29 '15 at 21:59
  • $\begingroup$ So you take the Church–Turing thesis to be a statement about intuition? mathworld.wolfram.com/Church-TuringThesis.html is clear that there are multiple competing interpretations of the Church–Turing thesis. I’m happy to accept that yours is one of them, although I don’t see any way to reason with it since we don’t have any theorems about intuition. $\endgroup$ – Anders Kaseorg Sep 30 '15 at 2:01
  • $\begingroup$ @DavidRicherby, do these edits make this answer more agreeable? $\endgroup$ – Anders Kaseorg Sep 30 '15 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.