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.
Here's something I've been wondering about, in the context of Solomonoff induction and uncomputable sequences.
I have a device that is either a halting oracle, or an ordinary Turing machine which gives the correct answer to the halting problem for all programs smaller than some finite length N but always outputs "does not halt" when asked to evaluate programs larger than N. If you don't know what N is and you don't have infinite time, is there a way to tell the difference between the actual halting oracle (which gives correct answers for all possible programs) and a "fake" halting oracle which starts giving wrong answers for some N that just happens to be larger than any program that you've tested so far?
The Kolmogorov complexity of an uncomputable sequence is infinite, so Solomonoff induction assigns it a probability of zero, but there's always a computable number with less than epsilon error, so would this ever actually matter?