Hypercomputation is a "cheat" that extends the capability of a Turing machine or quantum computer or cellular automaton by adding extra abilities. A standard method is "Oracle machines", Turing machines with an extra black box device that can be queried and give an output that normally would be uncomputable. For example, a halting oracle would tell the machine a bit encoding whether an input program would ever terminate. Such "hypercomputation" machines can calculate various forms of uncomputable outputs.

My questions are:

Is hypercomputation compatible with our laws of physics? What about other incomputable things like Russell's set (things which its result is not computable because it does not exist)? Or what about other uncomputable/illogical/impossible/non-existent/inconsistent things? Are there hypercomputational systems that could encode/compute them?

Thank you for your help

migrated from cstheory.stackexchange.com Aug 6 at 13:33

This question came from our site for theoretical computer scientists and researchers in related fields.

  • Russel's paradox shows that a certain definition is inconsistent with itself and thus doesn't yield a set, given universally accepted axioms. How would "hypercomputation" resolve that contradiction, even with a "universal oracle" that can "answer any question"? – Solomonoff's Secret Aug 6 at 14:26
  • @Solomonoff'sSecret That's what I'm asking. With oracles you can't do that. But is there any other type of hypercomputational device that could do that? – bautzeman Aug 7 at 13:18
  • I suppose if your hypercomputational device can invalidate mathematical logic it can solve Russel's Paradox, the halting problem, etc. But in that universe how can we reason about anything? – Solomonoff's Secret Aug 7 at 13:22

It is a little hard to say for sure since since one has not found a final Theory Of Everything in physics. Mostly it seems that hypercomputation is physically impossible.

On the other hand, an amusing development is the work of Nemeti et al. on using time travel (closed timelike curves) to do hypercomputation.

The so-called Malament-Hogarth spacetimes are known for exactly this --- that one can compute forever in them and thus solve the halting problem.

Hogarth worked on this in the 90s and Welch showed that even a larger class of problems than those solvable using the halting problem (all hyperarithmetic problems) can be solved in MH-spacetimes. This does not include all oracles though, as there are uncountably many oracles and only countably many hyperarithmetic ones.

(As for things that are logically impossible, like Russell's set, they are also physically impossible since "physics obeys logic".)

  • Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Aug 10 at 1:28

Not only is hypercomputation believed to be physically impossible, but even more ambitiously, some people working at the intersection of physics and computer science think that P!=NP might be a physical principle.

  • Since this is not a formal claim, but rather a claim of the type "some people claim X", I don't really need a source (or could just cite myself as someone who claims X). However, see this scottaaronson.com/papers/npcomplete.pdf – Aryeh Aug 7 at 22:26

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.