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
-
$\begingroup$ 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"? $\endgroup$Reinstate Monica– Reinstate Monica2018年08月06日 14:26:43 +00:00Commented Aug 6, 2018 at 14:26
-
$\begingroup$ @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? $\endgroup$bautzeman– bautzeman2018年08月07日 13:18:12 +00:00Commented Aug 7, 2018 at 13:18
-
$\begingroup$ 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? $\endgroup$Reinstate Monica– Reinstate Monica2018年08月07日 13:22:47 +00:00Commented Aug 7, 2018 at 13:22
2 Answers 2
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".)
-
$\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$2018年08月10日 01:28:23 +00:00Commented Aug 10, 2018 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.
-
$\begingroup$ 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 $\endgroup$Aryeh– Aryeh2018年08月07日 22:26:09 +00:00Commented Aug 7, 2018 at 22:26
Explore related questions
See similar questions with these tags.