= 27d567bc2d48d9f40e9ccc20ea370b15)
fezziwig comments on From the "weird math questions" department... - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (49)
Wouldn't it be easier to just generate a single program of size > N that halts by construction?
From the OP: "you don't know what N is." But, yes, you don't have to do the "step simulation", you are right. You can just check a single known halting program of every length, starting at 1, and increasing. Eventually you will catch the oracle in a lie.
See also: thomblake's comment below, which gives the same algorithm.
This is not a decision algorithm: if the oracle actually is real, your program will never terminate.
Edit: I guess you realize this already, but there are a few confused comments from other people here, so I will not retract this.
I am aware that this is not a decision algorithm. I said in my original comment that the set is recursively enumerable, and I also said that the algorithm will not terminate on true oracles. That is, we can list the fake oracles, but we cannot decide on the fake status of an oracle in finite time. This is what recursively enumerable means: http://en.wikipedia.org/wiki/Recursively_enumerable_set.
This is different from "recursive" (http://en.wikipedia.org/wiki/Recursive_set) where we can decide on membership in finite time.
I'm pretty sure that there is a method to determine the fake status of any oracle in finite time.
If there is such a method, it has to get around cousin_it's argument below. I believe you can only enumerate fake oracles, not answer if an oracle is fake or real, in finite time.
Right.