5 ms·

Maybe I'm biased, but I generally view posts about hypercomputation with skepticism. From The Myth of Hypercomputation[1]: > Under the banner of "hypercomputat

Maybe I'm biased, but I generally view posts about hypercomputation with skepticism. From The Myth of Hypercomputation[1]: > Under the banner of "hypercomputation" various claims are being made for the feasibility of modes of computation that go beyond what is permitted by Turing computability. In this article it will be show n that such claims fly in the face of the inability of all currently accepted physical theories to deal with infinite precision real numbers. When the claims are viewed critically, it is seen that they amount to little more than the obvious comment that if non-computable inputs are permitted, then non-computable outputs are attainable. The original idea in Turing's thesis was that the Turning Machine was something that could actually be implemented, and indeed you can find many examples of people's side projects where such machines can be made and can actually compute things. On the other hand, hypercomputation has no physical basis. So what's the point of using it to model anything real? It's next to useless. [1]: http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf

throwawayjava 9y ago
> On the other hand, hypercomputation has no physical basis The author repeatedly makes the point that we don't know, for sure, that this is the case. And that "we haven't built it yet", sans additional explanation, is pretty shoddy evidence for the non-existence of something. And that, if such a thing did exist, its existence may well be "very fundamental to the structure of the universe and should not be ignored". I agree with both you and the author. I don't think we'll ever build device capable of general-purpose "harnessable" hypercomputation. And I don't think any of the ideas described in this paper are in any meaningful sense physically realizable. But I also allow the possibility that I am wrong, especially on the first count. And if I am wrong, even just on the first count, then some of the theory surveyed in this paper might turn out to be useful.
- throwaway613834 9y ago
  Isn't Heisenberg's uncertainty principle sufficiently compelling? If you can't measure anything with arbitrary accuracy then that seems more than enough reason to assume you can't go beyond finite (digital) accuracy.
  - deepnotderp 9y ago
    The uncertainty principle in the strictest form is only technically present in wave-like systems, with the most prominent example being of course, quantum mechanical particles and their wave functions.
    - throwaway613834 9y ago
      That sounds like the real world we live in, doesn't it?
      - adrianratnapala 9y ago
        I think so, but the observation is not without loopholes. For example, classical field equations apparently can behave in non-computable ways, so long as their initial conditions are sufficiently wierd. I'm not sure if QM as we undestand it can handle such fields: but then "as we understand it" is a bit too limiting. So why haven't we observed these wierd non-computable fields? My guess is that it's because they don't exist. But it might be that we just haven't recognized them, perhaps some of those puzzling things in physics -- like QM perhaps itself is caused by naughty non-computable stuff going on where we haven't yet recognized it.
        pas 9y ago
        Could you expand on what non-computability means for a field? Is it sort of like the n-body problem of classic chaotic behavior?
        adrianratnapala 9y ago
        Re, chaotic behaviour: I don't think there is any simple similarity. Chaotic systems are computable in that you could in principle keep throwing more bytes and CPU cycles at it to get the error down to any bound you like. Regarding the first question, I am only repeating pop-science here. I've read (In something by Roger Penrose, presumably The Emperors New Mind, but maybe in The Road to Reality) that the Maxwell Equations are uncomputable only if the initial conditions are functions that don't have Fourier transforms. So really it is the field dynamics that are non-computable. I might have been talking nonsense when I the fields themselves were non-computable. But then again, the kinds of functions that don't have a Fourier transforms are also very rough, jaggedy things that probably can't be approximated by any algorithm. And speaking of rough jaggedy functions, that's what you get if you evolve a chatoic system to infinity. So maybe there is some connection after all, but it is well beyond my understanding.
- deepnotderp 9y ago
  > The author repeatedly makes the point that we don't know, for sure, that this is the case. And that "we haven't built it yet", sans additional explanation, is pretty shoddy evidence for the non-existence of something. The Bekenstein bound (https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound) and the Holographic Principle (albeit the latter not being a concrete part of physics yet) provide strong reasons as to why analog computing is not a viable path to the realization of "hypercomputation". Besides, a few loopholes nonwithstanding (https://pdfs.semanticscholar.org/a4b2/4409635c442b45f6fa42719925206786d287.pdf https://pdfs.semanticscholar.org/a4b2/4409635c442b45f6fa4271...), the physical existence of legitimate hypercomputation stands in almost direct opposition to the Church-Turing thesis.
- dwringer 9y ago
  There was a linked page here on HN a couple of months ago [1][2] with (I thought) an interesting overivew of this topic. [1] https://plato.stanford.edu/entries/computation-physicalsystems/#Hyp https://plato.stanford.edu/entries/computation-physicalsyste... [2] https://news.ycombinator.com/item?id=14773808 https://news.ycombinator.com/item?id=14773808
- naasking 9y ago
  > And that "we haven't built it yet", sans additional explanation, is pretty shoddy evidence for the non-existence of something. It's not claimed sans explanation. Hypercomputation would break a lot of physics. Others have mentioned the Bekenstein Bound, but just consider just basic concepts like signal to noise ratios. You'd need infinitely precise detectors for hypercomputation, detectors capable of distinguishing literally any signal, not matter how small, among any amount of noise, no matter how overwhelming. These properties simply stretch credulity, to say the least.
setra 9y ago
Your critique of hypercomputation applies all the same to Turing complete machines. A Turing machine can never be implemented and is a totally theoretical model. At best we can implement a class of machine below called a "Linear bounded Turing machine". For these machines the halting problem is solvable (it can just take a while). You could even implement a linear bounded Turing machine as an FSM it would just take an ungodly number of states.
- eximius 9y ago
  This is unintuitive to me. Source? (I can understand why we might not be able to build a Turing machine because we don't have infinite tape, etc, but if a program never halts but merely needs finite space, how do you prove that, in general?)
  - monochromatic 9y ago
    There are only finitely many states. Detect loops.
    - eximius 9y ago
      Okay. "Loop detected. It terminates conditionally on the value of `a`". I would think that deciding if a loop halts is equivalent to the halting problem (just wrap your program in a loop). Merely detecting loops seems insufficient.
      - anewhnaccount2 9y ago
        I think the answer is you can solve the halting problem if you have finite memory. You just need to consider every possible memory value. Eventually no new memory values can be introduced, so the next state must be one of the already inspected memory values. Of course all this takes at least exponential time and so is outside our normal computability assumptions.
        gizmo686 9y ago
frankmcsherry 9y ago
> On the other hand, hypercomputation has no physical basis. So what's the point of using it to model anything real? It's next to useless. Plenty of mathematics does not "model anything real", but you may still want to understand it. The paper starts with an analogy to non-Euclidean geometry, which once "had no physical basis", until we learned more about the universe and found that it did. Mathematics isn't a pitch deck.
marcosdumay 9y ago
It's just another case of abstract Math that nobody could find a use for. It does not look very useful from the start because there are too little consequences of any feature decision, but it's not completely unlike most of pure Math. If anything is a problem it is the attractive name, that pushes non-technical journalists into paying attention to it.

throwawayjava 9y ago

> On the other hand, hypercomputation has no physical basis The author repeatedly makes the point that we don't know, for sure, that this is the case. And that "we haven't built it yet", sans additional explanation, is pretty shoddy evidence for the non-existence of something. And that, if such a thing did exist, its existence may well be "very fundamental to the structure of the universe and should not be ignored". I agree with both you and the author. I don't think we'll ever build device capable of general-purpose "harnessable" hypercomputation. And I don't think any of the ideas described in this paper are in any meaningful sense physically realizable. But I also allow the possibility that I am wrong, especially on the first count. And if I am wrong, even just on the first count, then some of the theory surveyed in this paper might turn out to be useful.

throwaway613834 9y ago
Isn't Heisenberg's uncertainty principle sufficiently compelling? If you can't measure anything with arbitrary accuracy then that seems more than enough reason to assume you can't go beyond finite (digital) accuracy.
- deepnotderp 9y ago
  The uncertainty principle in the strictest form is only technically present in wave-like systems, with the most prominent example being of course, quantum mechanical particles and their wave functions.
  - throwaway613834 9y ago
    That sounds like the real world we live in, doesn't it?
    - adrianratnapala 9y ago
      I think so, but the observation is not without loopholes. For example, classical field equations apparently can behave in non-computable ways, so long as their initial conditions are sufficiently wierd. I'm not sure if QM as we undestand it can handle such fields: but then "as we understand it" is a bit too limiting. So why haven't we observed these wierd non-computable fields? My guess is that it's because they don't exist. But it might be that we just haven't recognized them, perhaps some of those puzzling things in physics -- like QM perhaps itself is caused by naughty non-computable stuff going on where we haven't yet recognized it.
      - pas 9y ago
        Could you expand on what non-computability means for a field? Is it sort of like the n-body problem of classic chaotic behavior?
        adrianratnapala 9y ago
        Re, chaotic behaviour: I don't think there is any simple similarity. Chaotic systems are computable in that you could in principle keep throwing more bytes and CPU cycles at it to get the error down to any bound you like. Regarding the first question, I am only repeating pop-science here. I've read (In something by Roger Penrose, presumably The Emperors New Mind, but maybe in The Road to Reality) that the Maxwell Equations are uncomputable only if the initial conditions are functions that don't have Fourier transforms. So really it is the field dynamics that are non-computable. I might have been talking nonsense when I the fields themselves were non-computable. But then again, the kinds of functions that don't have a Fourier transforms are also very rough, jaggedy things that probably can't be approximated by any algorithm. And speaking of rough jaggedy functions, that's what you get if you evolve a chatoic system to infinity. So maybe there is some connection after all, but it is well beyond my understanding.
deepnotderp 9y ago
> The author repeatedly makes the point that we don't know, for sure, that this is the case. And that "we haven't built it yet", sans additional explanation, is pretty shoddy evidence for the non-existence of something. The Bekenstein bound (https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound) and the Holographic Principle (albeit the latter not being a concrete part of physics yet) provide strong reasons as to why analog computing is not a viable path to the realization of "hypercomputation". Besides, a few loopholes nonwithstanding (https://pdfs.semanticscholar.org/a4b2/4409635c442b45f6fa42719925206786d287.pdf https://pdfs.semanticscholar.org/a4b2/4409635c442b45f6fa4271...), the physical existence of legitimate hypercomputation stands in almost direct opposition to the Church-Turing thesis.
dwringer 9y ago
There was a linked page here on HN a couple of months ago [1][2] with (I thought) an interesting overivew of this topic. [1] https://plato.stanford.edu/entries/computation-physicalsystems/#Hyp https://plato.stanford.edu/entries/computation-physicalsyste... [2] https://news.ycombinator.com/item?id=14773808 https://news.ycombinator.com/item?id=14773808
naasking 9y ago
> And that "we haven't built it yet", sans additional explanation, is pretty shoddy evidence for the non-existence of something. It's not claimed sans explanation. Hypercomputation would break a lot of physics. Others have mentioned the Bekenstein Bound, but just consider just basic concepts like signal to noise ratios. You'd need infinitely precise detectors for hypercomputation, detectors capable of distinguishing literally any signal, not matter how small, among any amount of noise, no matter how overwhelming. These properties simply stretch credulity, to say the least.

setra 9y ago

Your critique of hypercomputation applies all the same to Turing complete machines. A Turing machine can never be implemented and is a totally theoretical model. At best we can implement a class of machine below called a "Linear bounded Turing machine". For these machines the halting problem is solvable (it can just take a while). You could even implement a linear bounded Turing machine as an FSM it would just take an ungodly number of states.

eximius 9y ago
This is unintuitive to me. Source? (I can understand why we might not be able to build a Turing machine because we don't have infinite tape, etc, but if a program never halts but merely needs finite space, how do you prove that, in general?)
- monochromatic 9y ago
  There are only finitely many states. Detect loops.
  - eximius 9y ago
    Okay. "Loop detected. It terminates conditionally on the value of `a`". I would think that deciding if a loop halts is equivalent to the halting problem (just wrap your program in a loop). Merely detecting loops seems insufficient.
    - anewhnaccount2 9y ago
      I think the answer is you can solve the halting problem if you have finite memory. You just need to consider every possible memory value. Eventually no new memory values can be introduced, so the next state must be one of the already inspected memory values. Of course all this takes at least exponential time and so is outside our normal computability assumptions.
      - gizmo686 9y ago

frankmcsherry 9y ago

> On the other hand, hypercomputation has no physical basis. So what's the point of using it to model anything real? It's next to useless. Plenty of mathematics does not "model anything real", but you may still want to understand it. The paper starts with an analogy to non-Euclidean geometry, which once "had no physical basis", until we learned more about the universe and found that it did. Mathematics isn't a pitch deck.

marcosdumay 9y ago

It's just another case of abstract Math that nobody could find a use for. It does not look very useful from the start because there are too little consequences of any feature decision, but it's not completely unlike most of pure Math. If anything is a problem it is the attractive name, that pushes non-technical journalists into paying attention to it.