Roger Penrose is the Rouse Ball Professor of Mathematics at the University of Oxford. E.g. he’s the inventor of Penrose Tiles, which can cover a plane but only aperiodically (nice effect!). And he has proved, rigorously!, that you are smarter than him. Or, to be ultra-precise, he has proved that there are Mathematical Truths™ that you can easily see but he cannot. In this posting I shamelessly reproduce his proof.
Assuming a programming language where a program cannot crash and where there is no Undefined Behavior (i.e. this is not C++), let C0, C1, C2, C3, C4, C5 and so on be all possible computer programs that take a single non-negative integer n as input. Let Cq(n) denote the running of computer program Cq with n as input. For Penrose’s proof the main question is whether this program execution ever terminates, or not.
Let A be a soundproof box that contains Roger Penrose, who may not always hit on a correct answer to a question, but will never respond with an incorrect answer.
Box A sports a dual screen computer-like interface where you can input two numbers q and n on screen 1. Inputting the two numbers “runs” A(q, n), whereby Roger Penrose inside will ponder the question “will Cq(n) ever terminate?”. When or if Roger Penrose determines that Cq(n) cannot ever terminate he’ll press an internal button that causes screen 2 to display a four-color dragon curve.
The dragon curve display, signifying that Cq(n) cannot ever terminate, is the only possible response from box A. We regard this response (if it occurs) as the A “computation” having “terminated”, just as with a Cq program. It just helps to employ the same terminology as with the computer programs; nothing more is implied.
- If A(q, n) terminates then Cq(n) does not terminate.
Now, since Roger’s actions, or lack thereof, can be done by a computer program (any physical system can be emulated to any chosen degree of accuracy by a computer program), choose a k selecting a program such that for any n
- A(n, n) = Ck(n)
Then choosing n = k yields, from (A),
- If A(k, k) terminates then Ck(k) does not terminate
I.e. if A(k, k) terminates then A(k, k) does not terminate. From this you easily conclude that A(k, k) cannot ever terminate. For if it did then you’d have a contradiction at hand.
However, that A(k, k) does not terminate means that Roger Penrose inside the A box does not ever press that button causing a dragon curve to appear. So, Roger Penrose failed to see that A(k, k) cannot terminate. While you could see it easily! 🙂
Some possible refutations:
(1) Perhaps Roger Penrose cannot be emulated by a computer program?
(2) A computer program reacting the same as Roger Penrose in that box would have to cater for any amplification of small effects and so would have to simulate every fundamental particle of Roger, the inside of the box, and in particular of the communication to Roger of the k that represents this program (and himself and the box and itself).
(3) Or, perhaps Roger Penrose did see that A(k, k) cannot terminate, but also realized that if he pushed the button then he would be saying that he didn’t push the button, which would be false, an incorrect response.
Refutation (1) invokes a mystical dimension.
Refutation (2) goes to both (2a) the possibly infinite size of program k, which in a sense must contain a model of itself, and (2b) the dynamic ESP-like aspect of that program’s model having to incorporate in excruciating atomic detail the longwinded future event of k being communicated to itself (that is, to Penrose inside the box). But these problems are perhaps not unsurmountable. At least the size problem is just the well known “contains description of self” problem, solved by any first-year student writing a program that outputs its own source code.
Refutation (3) is a logical consequence of the setup. The proof assumes that Roger does not have the option of communicating a false answer, that he cannot lie. And so his proof has constrained him so that he cannot communicate his insight…
I once ran into a beautiful short version of (3) on the net, somewhere. It goes like this. In a Roger Penrose lecture with a large audience, you stand up and ask the following question. Given G = “Roger Penrose will never communicate that this sentence, G, is true”, is G true or not? Roger cannot truthfully say that G is true, because then it’s false. And you and everybody in the audience can easily see this. But Roger (our sympathies lie with him!) cannot say so, he cannot even imply it, and so he’s cast as one who cannot see the truth of G – which truth is evident to even the most slow-witted in the audience!
But – uh – wasn’t that what he already proved?