4 ms·

I conjecture that hypercomputation is impossible for the following simple reason. If you could solve the Halting Problem [1], then you could build a "living" co

I conjecture that hypercomputation is impossible for the following simple reason. If you could solve the Halting Problem [1], then you could build a "living" contradiction, where a machine halts if and only if it does not halt. (See proof in [2]). It won't be a mere description of a paradox, it would be an actual one. If contradictions are possible (something we implicitly believe to be impossible), then Reality is far stranger than we ever suspected or observed. [1] https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem [2] https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X https://www.amazon.com/Introduction-Theory-Computation-Micha...

eighthnate 9y ago
That's the accepted theory for sure. It's what every CS student learns. But never say never. "Reality/logic/math" can be a lot stranger than you think. There used to be a time when we thought that infinity ( aka countable infinity ) was the largest number. Turns how there are bigger infinities. And of course quantum mechanics. The duality of light ( both a wave and a particle ).
- trishankkarthik 9y ago
  But never say never. "Reality/logic/math" can be a lot stranger than you think. I understand it's a Black Swan kind of problem, but I don't think we live in that reality. Please show me a contradiction. The ramifications would be stupendous, to say the least. There used to be a time when we thought that infinity ( aka countable infinity ) was the largest number. Turns how there are bigger infinities. Yes, and we know how to build Turing machines that use countable infinity. Please show me a machine that actually uses bigger infinities. Please hypercompute the digits of a real number that cannot be computed by a Turing machine. And of course quantum mechanics. The duality of light ( both a wave and a particle ). Universal quantum computers are faster than classical computers, but they are no more powerful (they are not known to be able to hypercompute).
  - eighthnate 9y ago
    Why are you getting defensive? I agree with you more or less. All I said was reality can be stranger than we initially believed possible and showed you examples in other fields ( math, physics ) where "reality" got turned upside down. Computer science is a fairly new field. It's within the realm of possibility that reality can be turned upside too. I'm not said it is or will be, but it can. Okay?
    - trishankkarthik 9y ago
      I'm not getting defensive, my friend. I was merely challenging you to think through the logical implications of hypercomputation. What many people miss is this: hypercomputation leads to living paradoxes. They might then have to bend over backwards to explain why these paradoxes are not possible, but that leaves the question of why some things are hypercomputable, and some are not.
      - eighthnate 9y ago
        I wasn't even talking about hypercomputation specifically. I was talking more in generalities about computer science and things we hold to be "reality/absolutes".
Dylan16807 9y ago
A hypercomputer that is capable of solving turing-halting problems but not hyper-halting problems is both non-contradictory and extremely useful.
- trishankkarthik 9y ago
  Interesting, thanks for bringing this to my attention! In turn, this raises the question of hyper-hyper-computers more powerful than hypercomputers: https://cs.stackexchange.com/a/4871 https://cs.stackexchange.com/a/4871 It reminds me of what Whitehead and Russell tried to achieve with Principia Mathematica, to try to eradicate paradoxes altogether using hierarchies of sets, until Gödel came along.
  - trishankkarthik 9y ago
    Wait a minute --- this hypercomputer is still impossible by my conjecture. For if it were possible, then you could use it as an oracle to build that self-contradicting Turing machine halts if and only if it does not halt.
    - dllthomas 9y ago
      "TM with oracle" can be more powerful than a Turing machine. As long as this halting oracle can only apply to ordinary Turing machines (without oracles) I don't see a contradiction.
      - trishankkarthik 9y ago
        That seems to me an unnecessary, artificial restriction. Then it's incomplete: it doesn't solve the Halting Problem. That's the point: either the system is incomplete or inconsistent.
        dllthomas 9y ago
        It solves the halting problem for Turing machines. Revisit Dylan16807's comment upthread. I use "solves" somewhat advisedly - we're postulating something that may very well not exist; it's just that it's not obviously inconsistent for it to exist in the way that it would be if it had an oracle for its own class of machine.

eighthnate 9y ago

That's the accepted theory for sure. It's what every CS student learns. But never say never. "Reality/logic/math" can be a lot stranger than you think. There used to be a time when we thought that infinity ( aka countable infinity ) was the largest number. Turns how there are bigger infinities. And of course quantum mechanics. The duality of light ( both a wave and a particle ).

trishankkarthik 9y ago
But never say never. "Reality/logic/math" can be a lot stranger than you think. I understand it's a Black Swan kind of problem, but I don't think we live in that reality. Please show me a contradiction. The ramifications would be stupendous, to say the least. There used to be a time when we thought that infinity ( aka countable infinity ) was the largest number. Turns how there are bigger infinities. Yes, and we know how to build Turing machines that use countable infinity. Please show me a machine that actually uses bigger infinities. Please hypercompute the digits of a real number that cannot be computed by a Turing machine. And of course quantum mechanics. The duality of light ( both a wave and a particle ). Universal quantum computers are faster than classical computers, but they are no more powerful (they are not known to be able to hypercompute).
- eighthnate 9y ago
  Why are you getting defensive? I agree with you more or less. All I said was reality can be stranger than we initially believed possible and showed you examples in other fields ( math, physics ) where "reality" got turned upside down. Computer science is a fairly new field. It's within the realm of possibility that reality can be turned upside too. I'm not said it is or will be, but it can. Okay?
  - trishankkarthik 9y ago
    I'm not getting defensive, my friend. I was merely challenging you to think through the logical implications of hypercomputation. What many people miss is this: hypercomputation leads to living paradoxes. They might then have to bend over backwards to explain why these paradoxes are not possible, but that leaves the question of why some things are hypercomputable, and some are not.
    - eighthnate 9y ago
      I wasn't even talking about hypercomputation specifically. I was talking more in generalities about computer science and things we hold to be "reality/absolutes".

Dylan16807 9y ago

A hypercomputer that is capable of solving turing-halting problems but not hyper-halting problems is both non-contradictory and extremely useful.

trishankkarthik 9y ago
Interesting, thanks for bringing this to my attention! In turn, this raises the question of hyper-hyper-computers more powerful than hypercomputers: https://cs.stackexchange.com/a/4871 https://cs.stackexchange.com/a/4871 It reminds me of what Whitehead and Russell tried to achieve with Principia Mathematica, to try to eradicate paradoxes altogether using hierarchies of sets, until Gödel came along.
- trishankkarthik 9y ago
  Wait a minute --- this hypercomputer is still impossible by my conjecture. For if it were possible, then you could use it as an oracle to build that self-contradicting Turing machine halts if and only if it does not halt.
  - dllthomas 9y ago
    "TM with oracle" can be more powerful than a Turing machine. As long as this halting oracle can only apply to ordinary Turing machines (without oracles) I don't see a contradiction.
    - trishankkarthik 9y ago
      That seems to me an unnecessary, artificial restriction. Then it's incomplete: it doesn't solve the Halting Problem. That's the point: either the system is incomplete or inconsistent.
      - dllthomas 9y ago
        It solves the halting problem for Turing machines. Revisit Dylan16807's comment upthread. I use "solves" somewhat advisedly - we're postulating something that may very well not exist; it's just that it's not obviously inconsistent for it to exist in the way that it would be if it had an oracle for its own class of machine.