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