3 ms·
There are plenty of oracle solutions to the halting problem. The simplest one uses the bits of Chaitin’s constant, an incomputable number, to solve Halting in p
by scythe 7y ago
There are plenty of oracle solutions to the halting problem. The simplest one uses the bits of Chaitin’s constant, an incomputable number, to solve Halting in polynomial time. Of course, these solutions cannot be physically implemented (eg. calculating N bits of Chaitin’s constant requires solving the halting problem for all N-bit machines, so the algorithm is “circular”).
- 9nGQluzmnq3M 7y agoYes, but my layman's understanding is that the oracle is a theoretical construct that knows in advance what programs halt and what don't -- but as you note, the real-world issue is that such oracles don't exist. My question remains, how does this tie back to the proof? Is there a path to building such an oracle now?
- dwohnitmok 7y agoNo there is still no path to constructing such an oracle. The paper basically presents a result built off of a less trustworthy oracle (or set of oracles) that can potentially lie, but that still has unlimited computational power.