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.
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.