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.
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!).
how do you know in finite time whether it is a true oracle or if you haven’t yet found N?
Write a short program that applies my method to an oracle. (Don’t run it yet)
Use my method to determine whether the oracle is “true” or “fake” for N = your program length. If “fake”, then you’re done.
If “true” for N = your program length, then ask the oracle whether your program will halt. If so, then it’s “fake”.
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.
Write a program which halts if our oracle is false in the specified manner, and which does not halt if the oracle is true
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.
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.
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”
Write a short program that applies my method to an oracle. (Don’t run it yet)
Use my method to determine whether the oracle is “true” or “fake” for N = your program length. If “fake”, then you’re done.
If “true” for N = your program length, then ask the oracle whether your program will halt. If so, then it’s “fake”.
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:
Make your best guess for N and check it.
If the test comes out “fake”, perform a binary search from 1 (or the highest known “true” value) to N
If the test comes out “true”, double N and goto 1.
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.