Hacker News new | ask | show | jobs
by baddox 4342 days ago
Technically P=NP is just about Turing machines (and thus all Turing complete systems, which includes all the computers humans have produced). As far as I know there is no evidence of real super-Turing systems, but the concept has been theorized.

http://en.wikipedia.org/wiki/Hypercomputation
1 comments
dllthomas 4341 days ago
Right. "There exists a device that can solve NP problems in P time" is a different statement than "P=NP".

Regarding "Hypercomputation" in particular, I've typically encountered it in the context of "solving problems a TM can't solve" rather than "solving problems a TM can solve but asymptotically faster" - is it actually used for both? A skim of the article didn't clarify.

link
baddox 4341 days ago
That's a good point. The first sentence of the Wikipedia article says "Hypercomputation or super-Turing computation refers to models of computation that go beyond, or are incomparable to, Turing computability." The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to. :)

Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster.

link
dllthomas 4341 days ago
'The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to.'

I totally agree, which is part of why the article didn't clear it up.

"Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster."

A Zeno machine, for sure. It is not immediately clear to me that this necessarily holds for anything that can solve the halting problem - what about a TM plus a halting problem oracle that would tell you in 2^(size of TM) whether a TM halts?

Of course the real question is whether asymptotically faster is enough to be "hypercomputation". Necessity is also interesting, but not the same thing.

link