2 ms·
Yes, 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
by 9nGQluzmnq3M 7y ago
Yes, 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.