Hacker News new | past | comments | ask | show | jobs | submit login

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.


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.


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




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: