4 ms·
I don't think so. If that was the case, then for any program we could compute its length n, and then ask the all-knowing oracle the value of BB(n). And knowing
by alexmolas 4y ago
I don't think so. If that was the case, then for any program we could compute its length n, and then ask the all-knowing oracle the value of BB(n). And knowing BB(n) for any n we could solve the Halting Problem, but we know that the Halting Problem is unsolvable. Therefore we must conclude that such an all-knowing oracle can't exist.
- NotYourLawyer 4y agoYes, that’s my point. The all-knowing oracle could also just tell you whether or not your program halts.