tgb comments on From the "weird math questions" department... - Less Wrong

5 Post author: CronoDAS 09 August 2012 07:19AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (49)

You are viewing a single comment's thread. Show more comments above.

Comment author: tgb 10 August 2012 02:59:02AM 0 points [-]

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?

Comment author: IlyaShpitser 11 August 2012 05:09:30PM 0 points [-]

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.