You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Pfft comments on Polarized gamma rays and manifest infinity - Less Wrong Discussion

16 Post author: rwallace 30 July 2011 06:56AM

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

Comments (50)

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

Comment author: Pfft 01 August 2011 11:43:33PM *  1 point [-]

I don't think the situation is comparable.

Recall that in the chess case the setup is this: the verifier is given a string of n random bits, asks P(n) interactive questions to the alien, and then says yes or no. If White can force a win in chess the verifier says yes in 2/3s of the cases, while if White cannot force a win the verifier says yes in only 1/3d of the cases.

It's a deep result that you can set up a verification protocol like this for any problem in PSPACE. But it's easy to see that it only works if the problem is in PSPACE: using P(n) space, the alien can simulate all possible question-answer interactions with the verifier, and give the answers that will make the verifier answer yes if there are any at all. So you could never use a protocol like this to prove that you possess a halting oracle, since even without an oracle you can do a finite amount of computation to figure out what answers the verifier will accept.

I would guess this principle holds in general: no matter which particular notion of "proof" or "convincing" you settle on, it will ultimately involve running a finite computation to verify a purported proof. But such a procedure can always be fooled by another (longer) finite computation.

(Edit: corrected error in the description of the protocol)