= 27d567bc2d48d9f40e9ccc20ea370b15)
thomblake 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)
If N considers the program's length regardless of compressability, then you should be able to feed the "fake" halting oracle longer and longer programs that you already know will halt (like "print 1" "print 11" "print 111"). Since it actually gives reliable output after N, you can do something like a binary search (modified for infinite lists) to find its limit.
So, how do you know in finite time whether it is a true oracle or if you haven't yet found N?
If the oracle is fake, you will find out in finite time since eventually you will print N 1s, and the oracle will lie about that program. If the oracle is true, this method will never terminate. But I don't think there is a way for a Turing machine to check for a true oracle (only for a fake oracle!).
What if the finite time needed to determine N is greater than the finite time that you have available?
OP asked "is there a way" not "is there a fast way".
"In finite time" is not the same as "Using a halting process"
EDIT: Somehow, I wrote the above having forgotten that the fake oracle outputs "never halts" above N, not "will halt".
Alternatively, you could just keep applying the method up to N that you're concerned about - you will thus always know before trusting the oracle with a program of length N, whether it's true or fake.
Write a program which halts if our oracle is false in the specified manner, and which does not halt if the oracle is true (for example, a program which tests a trivial halting program of length ++ in a loop.) You don't run that program, but you do determine that our oracle gives a true answer for programs of that size, by testing a longer halting program of the trivial type.
You then test the oracle on that program- if the oracle says the program halts, it is a false oracle. If the oracle says that program does not halt, it is not a false oracle of the specific type described in the problem.
And it can be solved in constant time- you need to ask the oracle twice.
I didn't see that you didn't actually have to test the oracle with a program of length N+1; you only need to figure out how to ask the oracle what it would say when asked that question.
This is not a program, since the oracle is not a program, and so can't be called as a subroutine. Since this is not a program, it can't be given to the oracle.
By the way, one way of doing this is:
I don't think there's an optimal search algorithm for an infinite list of unknown distribution. Anyone know better?
That's a good one, for some priors about N. Any definition of "better" or "optimal" will be with respect to a prior about N. That prior can be unbounded and still produce good algorithms.
The obvious thing to tweak about your program is the "double N" constant; you could instead go to 3*N or something.
If you know your prior in detail, you'll want to make your next guess to split the remaining probability weight evenly, not just the numeric search space. (Similar in concept to arithmetic coding.) With a poor understanding of the prior, though, this is a very minor detail.