There is also a proof of this fact that uses a different paradox, Berry's paradox, which I heard from Ran Raz. Suppose that the halting problem were computable. Let $B(n)$ be the smallest natural number that cannot be computed by a C program of length $n$. That is, if $S(n)$ i...
The Surprise Examination Paradox and the Second Incompleteness Theorem
- Citation data:
Notices of the AMS, Vol: 57, Issue: 11, Page: 1454-1458
- Publication Year:
- Repository URL:
- Most Recent Tweet View All Tweets
We give a new proof for Godel's second incompleteness theorem, based on Kolmogorov complexity, Chaitin's incompleteness theorem, and an argument that resembles the surprise examination paradox. We then go the other way around and suggest that the second incompleteness theorem gives a possible resolution of the surprise examination paradox. Roughly speaking, we argue that the flaw in the derivation of the paradox is that it contains a hidden assumption that one can prove the consistency of the mathematical theory in which the derivation is done; which is impossible by the second incompleteness theorem.