In class, someone suggested why traditional mathematical proofs seem to differ from zero-knowledge proofs, probabilistically checkable proofs, (multi-prover) interactive proofs, quantum proofs, and all the other exotic types of proof studied in modern cryptography and complexity theory. Namely, with a traditional proof, “all the cards are on the table”: there’s nothing the verifier doesn’t get to see, and for which he or she is forced to make some assumption about the laws of physics and/or the limitations of the prover(s). But what exactly do we mean by “all the cards being on the table”? Suppose a proof is written out in a conventional way, but it’s a trillion lines long, so in practice it can only be checked by a computer—does that count as “all cards being on the table”? Or does a conscious person need to be able to understand the whole proof, “at a glance” so to speak? Where should we draw the line, and why? (Or is there no need to draw a line?)
Suppose we say that “all the cards on the table” with a conventional proof, but not with a proof that requires a quantum computer to verify. Does that imply that (as Niels Bohr argued) there’s still a fundamental role for classical concepts, even in a quantum-mechanical universe?
We discussed the arguments of Searle, Putnam, and other philosophers that the “meaning” of a computation is always observer-dependent—since merely by our choice of how to label inputs and outputs, we can interpret even a rock or a waterfall as computing anything at all (say, the next move in a chess game). Most CS folks have a very strong intuition that this argument is wrong, but why is it wrong? Does it have to do with some input/output labelings being “inherently more natural” than others? Or with the computational complexity of reducing chess to rock- or waterfall-simulation—i.e., with our intuition that all the actual work of computing chess moves would have to be done by the reduction itself, rather than by the rock or waterfall being “reduced” to? Or (as Chalmers says) with the various internal states of the rock or waterfall not having the right causal relations to one another? Or something else?
Are the various responses to the rock/waterfall argument mentioned above all basically the same? Can you suggest examples where some of the responses would work, but not others?
Are any of your answers different for the rock (which we could naïvely describe as “not computing anything”) than for the waterfall (which we could naïvely describe as “computing something complicated but uncontrollable”)?