Did you mean to write "for all programs that halt in less than (some constant multiple of) N steps", because what you wrote doesn't make sense.
Yes. Edited.
What if I give you a program that enumerates all proofs under PA and halts if it ever finds proof for a contradiction? There is no proof under PA that this program doesn't halt, so your fake oracle will return HALT, and then I will have reasonable belief that your oracle is fake.
That's cool. Can you do something similar if I change my program to output NOT-HALT when it doesn't find a proof?
Can you do something similar if I change my program to output NOT-HALT when it doesn't find a proof?
Consider a program that enumerates all proofs under PA of length up to N^c for some c. If it finds a contradiction, it loops forever, otherwise it halts. I have reasonable belief that it halts, but your fake oracle can't prove that it does using a proof of length at most N, if c is sufficiently large (see On the length of proofs of finitistic consistency statements in first order theories).
Or here's another way that doesn't depend on that result. Define...
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?