Sorry, got mixed up with cameroncowan. Anyway, to the original point:
You said "Once they've finished the proof, you record what's written on their paper, and reverse the entire simulation... Looking at what they wrote on the paper doesn't mean you have to communicate with them."
My interpretation--which may be wrong--is that you are suggesting that the person running the simulation record the state of the simulation at the moment the problem is solved, or at least the part of the simulator state having to do with the paper. However the process of extracting information out of the simulation -- saving state -- is irreversable, at least if you want it to survive rewinding the simulation.
To put differently, if the simulation is fully reversible, then you run it forwards, run it backwards, and that the end you have absolutely zero knowledge about what happened inbetween. Any preserved state that wasn't there at the beginning would mean that the process wasn't fully reversed.
Looking at the paper is communicating with the simulation. It maybe be a one-way communication, but that is enough.
I'm suggesting that the person running the simulation knows the state of the simulation at all times. If this bothers you, pretend everything is being done digitally, on a classical computer, with exponential slowdown.
Such a calculation can be done reversibly without ever passing information into the system.
Yet another exceptionally interesting blog post by Scott Aaronson, describing his talk at the Quantum Foundations of a Classical Universe workshop, videos of which should be posted soon. Despite the disclaimer "My talk is for entertainment purposes only; it should not be taken seriously by anyone", it raises several serious and semi-serious points about the nature of conscious experience and related paradoxes, which are generally overlooked by the philosophers, including Eliezer, because they have no relevant CS/QC expertise. For example:
Scott also suggests a model of consciousness which sort-of resolves the issues of cloning, identity and such, by introducing what he calls a "digital abstraction layer" (again, read the blog post to understand what he means by that). Our brains might be lacking such a layer and so be "fundamentally unclonable".
Another interesting observation is that you never actually kill the cat in the Schroedinger's cat experiment, for a reasonable definition of "kill".
There are several more mind-blowing insights in this "entertainment purposes" post/talk, related to the existence of p-zombies, consciousness of Boltzmann brains, the observed large-scale structure of the Universe and the "reality" of Tegmark IV.
I certainly got the humbling experience that Scott is the level above mine, and I would like to know if other people did, too.
Finally, the standard bright dilettante caveat applies: if you think up a quick objection to what an expert in the area argues, and you yourself are not such an expert, the odds are extremely heavy that this objection is either silly or has been considered and addressed by the expert already.