From the "weird math questions" department...

It's very possible that I misunderstood your question, but here's a stab at an answer.

Assume that you have such a testing procedure. First let's run it on a device that is actually a halting oracle. Presumably the procedure would ask the device a finite number of questions, receive correct answers to all of them, and then declare "yes, this is a halting oracle". Let N be the length of the longest question thus asked. Then a fake halting oracle with length limit N would also pass the procedure.

For any broken halting oracle there exists a broken halting oracle detector that identifies it and for any broken halting oracle detector there exists a broken halting oracle that escapes detection.

IF AND ONLY IF you know that the object is either a true or fake oracle: you can determine that it is oracular for all programs of some finite length X, where X is determined by the amount of time you want to spend feeding in n-length programs known to halt.

For any given X, you've identified that the oracle is true for X or less, but you cannot confirm that X > N, and thus cannot confirm whether the oracle is true or fake, simply that it will be true for all lengths X or less.

That said, if your goal is to evaluate program A, you can just run a known-halting problem of the same length past the oracle to confirm that it's valid for evaluation of this program. If you do this for each program you evaluate, then your results become "halts", "doesn't halt", "this is actually a fake oracle, oops", with 100% confidence :)

(I realize 100% confidence should never exist, but if there is the possibility of it being a true oracle, a fake oracle, or a different sort of fake oracle, then NONE of these conclusions is valid. So we get to play with a hypothetical super-certainty world where there's only true and fake oracles :))

Follow-up: Would AIXI (the ideal implementation of Solomonoff induction) do significantly worse at predicting the next digit of Chaitin's constant than a computable algorithm that "knows" that it's trying to predict the next digit of a specific uncomputable sequence with defined properties?

Also, for the lulz, I'd like to run AIXItl on "A Million Random Digits" and see if it really is algorithmically random.

The set of such oracles is at least recursively enumerable, I think. In order to detect that your oracle is not a true halting oracle for programs larger than N, all you must do is find a program larger than N that halts. If you have a proof that such a program halts, you simply feed it to your oracle, notice that the oracle is lying, and you are done.

But it's not hard to find such a program. Simply simulate all programs of length <= 1 for 1 steps, then all programs of length <= 2 for 2 steps, etc. At some finite point you will find a program of size >N that halts in k steps. If your oracle is a true halting oracle, this procedure will not terminate, of course.

cousin_it's argument below shows we can't do much better than recursively enumerable here.

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.

Are you allowed to write a program which calls the possible oracle as a function and which uses recursion, are you allowed to have multiple programs, and are you allowed to write to those programs? If so, I wonder if the series below would do. (I'm not going to suggest it works, until I have a few other people check it, and until I make sure that the psuedocode is understandable.)

Program A:

Call Program B;

if Possible Oracle(Program B)="halts" then do;

Add line "Print 'even more gibberish' to the beginning of Program B;

Call Program A;

end if;

else if Possible Oracle(Program B)="does not halt" then do;

print "Possible Oracle is a fake."

end if;

End Program A.

Program B:

Print 'even more gibberish';

End Program B.

And then after defining all of that, run Possible Oracle(Program A);

Let's say Possible Oracle is a 20 line fake.

It starts Running A to see if it halts. The first time it runs through the loop in A, it runs B, which is 1 line. It then tests B, which is 1 line. It reports correctly that B halts. Based on that, it adds 1 line to B, and runs B, which is now 2 lines. It then tests B again, which is 2 lines. It reports correctly that B halts.

(Later)

Based on that, it adds 1 line to B, and runs it again. B is 21 lines. It then tests B, which is 21 lines. It reports incorrectly that B does not halt. Prints "Possible Oracle is a fake.", and Program A ends, so it reports Program A halts. sure enough, it's a fake.

Let's say Possible Oracle is real.

It starts Running A to see if it halts. The first time it runs through the loop in A, it runs B, which is 1 line. It then tests B, which is 1 line. It reports correctly that B halts. Based on that, it adds 1 line to B, and runs B, which is now 2 lines. It then tests B again, which is now 2 lines. It reports correctly that B halts. Based on that, it adds 1 line to B, and tests it again...

(Later)

Program A, as far as I can tell, can't halt for a true oracle.

Let's Assume B gets to the point where it does not halt. then since Program A will run that Program B, Program A will never halt.

Let's Assume B never gets to the point where it never halts. then since Program A calls the possible oracle, it will report that Program B halts, and if that's the case, it calls an additional Program A instead of ending. The first Program A will never halt.

I think that should work, but unfortunately I don't have a fake oracle and a real oracle to use for testing.

Edit: Fixed line breaks

If I am allowed to use only exponentially more computing power than you (are far cry from a halting oracle), then I can produce outputs that you cannot distinguish from a halting oracle.

Consider the following program: Take some program P as input, and search over all proofs of length at most N, in some formal system that can describe the behaviour of arbitrary programs (ie first order PA) for a proof that P either does or does not halt. If you find a proof one way or the other, return that answer. Otherwise, return HALT.

This will return the correct answer for all programs of which halt in less than (some constant multiple of) N, since actually running the program until it halts provides a proof of halting. But it also gives the correct answer for a lot of other cases: for example there is a very short proof that "While true print 1".

Now, if I am allowed exponentially more computing power than you, then I can run this program with N equal to the number of computations that you are allowed to expend. In particular, any program that you query me on, I will either answer correctly, or give a false answer that you won't be able to call me out on.

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?

Can you re-phrase this please? I don't understand what you are asking.

but there's always a computable number with less than epsilon error, so would this ever actually matter?

Yes. There are programs that can neither be proven to halt nor to not halt. The knowledge that these do not halt would need to be specifically programmed in, and the K-complexity would increase for each one.

On the other hand, it's not exactly known how common these are. They might be pretty rare.

In any case, you could change it from shortest computer program to shortest definition, and thus get definable numbers instead of computable ones.

The only way to tell the difference between such a a machine and a halting oracle is to test a program larger than N which is known to halt.

So, no.