Hacker News Reader

Comment by trishankkarthik | Hacker News Reader

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

[2] https://www.amazon.com/Introduction-Theory-Computation-Micha...

View on HN

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 ).

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).

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?

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.

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".

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

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

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.

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.

"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.

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.

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.

We're talking past each other. Please revisit Sipser's proof for why the halting problem is TM-uncomputable, and you'll see what I mean.

> Please revisit Sipser's proof

In this kind of context, you should provide a link. This kind of thing can spill over into "You're wrong because you haven't done the work to see that I'm right", and minimizing the work you're pushing off shows good faith as well as increasing clarity that we're talking about the same thing.

I think it's more likely we're talking about different things than either of us failing to understand the relevant proofs. I'll take a look, though, when you've provided the link (and ideally some explanation of what you see as important).

The whole point of a hypercomputer is not being a Turing Machine. So yes, it can calculate things that are TM-uncomputable.

You can't use it to build a self-contradicting Turing Machine, because a hypercomputer cannot be emulated by a Turing Machine.

There is no "the" halting problem. Each class of machines has its own halting problem. The halting problem for turing machines is very hard. The halting problem for non-cyclic finite state automatons is very easy. A hypercomputer that can solve all halting problems is self-contradictory. A hypercomputer that can solve turing-or-weaker halting problems is not self-contradictory.

Reply on news.ycombinator.com