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.
I think there’s an assumption in this that isn’t quite spelled out by the question being asked: your argument holds if the lengths of the programs which you test the argument on are not a function of the oracle.
To say that more clearly, you state that for all L, if you give programs of length at most L to the maybe-oracle, then there exists a maybe-oracle for which N>L and hence that maybe-oracle goes undetected. But if we reverse the for-all and the there-exists, then we don’t have a true statement: there does not exist a maybe-oracle such that for all L we cannot detect it. So if the question allows us to ‘inspect’ the maybe-oracle and then pick L, it might be possible.
That said, I strongly suspect that there’s no coherent way to ‘inspect’ a maybe-oracle without knowing whether it is a Turing machine or not and I bet that the OP was intending for the oracle to be a ‘black box’ with nothing known other than the outputs that we ask it for. I initially wanted to make L a function of the length of the maybe-oracle—but what is the length of the true oracle given that it is not a Turing machine? If it is expressed as some ur-machine that includes Turing machines as a subset, then it might be possible to define a length and use this to determine an L.
Rice’s theorem makes me suspect that even this is not enough, but I’m not familiar enough with this field to say more. Thoughts?
Note that the halting problem isn’t very relevant here. You can take a much simpler problem, like computing the sum of two integers. By the same argument, it’s just as impossible to fully test a black box that claims to be an adding machine, but outputs garbage for inputs greater than some N. Moreover, you can’t always determine whether a box is an adding machine even if you’re allowed to look inside the box and inspect its algorithm, by Rice’s theorem.
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.
I think there’s an assumption in this that isn’t quite spelled out by the question being asked: your argument holds if the lengths of the programs which you test the argument on are not a function of the oracle.
To say that more clearly, you state that for all L, if you give programs of length at most L to the maybe-oracle, then there exists a maybe-oracle for which N>L and hence that maybe-oracle goes undetected. But if we reverse the for-all and the there-exists, then we don’t have a true statement: there does not exist a maybe-oracle such that for all L we cannot detect it. So if the question allows us to ‘inspect’ the maybe-oracle and then pick L, it might be possible.
That said, I strongly suspect that there’s no coherent way to ‘inspect’ a maybe-oracle without knowing whether it is a Turing machine or not and I bet that the OP was intending for the oracle to be a ‘black box’ with nothing known other than the outputs that we ask it for. I initially wanted to make L a function of the length of the maybe-oracle—but what is the length of the true oracle given that it is not a Turing machine? If it is expressed as some ur-machine that includes Turing machines as a subset, then it might be possible to define a length and use this to determine an L.
Rice’s theorem makes me suspect that even this is not enough, but I’m not familiar enough with this field to say more. Thoughts?
Oracles are not strings, and cannot be inspected. Typically what you do is consider a Turing machine that uses a particular oracle as a subroutine.
This comment confuses question length and program length.
Yeah, that’s what I kind of figured, too...
Note that the halting problem isn’t very relevant here. You can take a much simpler problem, like computing the sum of two integers. By the same argument, it’s just as impossible to fully test a black box that claims to be an adding machine, but outputs garbage for inputs greater than some N. Moreover, you can’t always determine whether a box is an adding machine even if you’re allowed to look inside the box and inspect its algorithm, by Rice’s theorem.