Bounded surprise exam paradox
A small fun thing I came up with this morning.
The surprise exam paradox goes as follows: “you’ll be given a surprise exam on one of the days next week, and you won’t figure out the date of the exam on the previous day”. Then you figure that the exam can’t be on Sunday as it’s the last day and you’d know it on Saturday, so it can’t be on Saturday and so on, ruling out all days. Then the exam happens on Wednesday and you’re surprised.
The standard solution, which I agree with, is to interpret it as a self-referential sentence S = “there is a natural number X from 1 to 7, such that from knowing any lower bound on X and also knowing S, it’s impossible to prove the value of X”. This isn’t a liar kind of paradox, because the self-reference in S only talks about provability, not truth. So we can take any formal theory that’s strong enough to talk about provability within itself (same conditions as Gödel’s theorems), convert S into a non-self-referential sentence by using the diagonal lemma, and observe that S is false. And from a falsehood anything follows, so for the student’s conclusions are only the student’s problem.
It’s a satisfying solution, but there’s a wrinkle. What if we interpret the teacher’s statement as being not about provability, but as a prediction of the future? Not “there’s no proof”, but “you specifically, as a deterministic algorithm running in finite time, will not find a proof”?
We can encode that by using two self-references instead of one. The student will be a program P, which on the evening of each day will enumerate all proofs in Peano arithmetic up to N symbols long, for some large N. The teacher’s statement S will be: “The program P, quoted here in full, won’t on any day find a proof that {S + knowledge of that day} implies the exam is the next day.” All self- and mutual references can again be resolved by using the diagonal lemma. So P will either find a proof or won’t. Which is it?
Well, if N is large enough, P can prove that the exam can’t happen on the last day, then on the day before and so on, by the same method as in the original paradox. So on the very first day P will prove that S is false, and also that S implies the exam will be on Monday, and S implies the exam will be on Tuesday, all of that at the same time. In other words, even if the student is a bounded deterministic program without logical omniscience, the teacher is still lying. The student will still prove from the teacher’s words that the exam will happen on a specific day, and also on another specific day, and also the moon is made of green cheese.
What about something like “The pupil won’t find a proof by start-of-day, that the day is exam day, if the day is in fact exam day.”
This way, the teacher isn’t denying “for any day”, only for the one exam day.
Can such a statement be true?
Well, the teacher could follow a randomized strategy. If the teacher puts 1/5th probability on each weekday, then there is a 1/5th chance that the exam will be on Friday, so the teacher will “lose” (will have told a lie), since the students will know it must be exam day. But this leaves a 4/5ths chance of success.
Perhaps the teacher should exclude Friday from the distribution, instead placing a 1/4th chance on each weekday before Friday. If we treat the situation game-theoretically, so we make the typical assumption that agents can know each other’s mixed strategies, then this would be a foolish mistake for the teacher—there’s now a 1/4th probability of lying rather than a 1/5th. (Instead, the teacher should place arbitrarily small but positive probability on Friday, to minimize chances of lying.)
But so long as we are staying in the deductive, realm, there is no reason to make that game-theoretic assumption. If the students and teacher are both reasoning in PA, then the students do not trust the teacher’s reasoning to be correct; so there is not common knowledge of rationality.
So it seems to me that in the purely deductive version of the problem, the teacher can keep their word; and in the game-theoretic version, the teacher can keep their word with arbitrarily high probability (so long as we are satisfied with arbitrarily small “surprise”).
Huh? It seems to me that in the deductive version the student will still, every day, find proofs that the exam is on all days.
I think it’s far simpler to realize that the meaning of “won’t figure out” is a bit ambiguous. The logic is sound that it won’t be a surprise on Friday, and given that, won’t be a surprise on Thursday, and given that, won’t be a surprise on Wednesday, etc. for all days. But it’s not a problem if you realize that there’s going to be a test anyway, it’s ONLY a lie about the conditions IF it happens on a Friday. The fact that it doesn’t happen on a friday allows the surprise to be consistent with the statement, WITHOUT any implication that every universe would be consistent with the statement.
The test-giver could have simply randomized among the 5 days. If it were Friday, they’d have lied about the conditions, but 80% of the time they’d have performed magic.
The test-taker can defeat it by predicting a day (psychologically, M-Th are best bets), and having a good chance of beating the game—the statement is “won’t figure out”, which is simply wrong if the taker DOES IT.
In context of boundaries/membranes, I’ve been thinking of how a lot of spurious proof issues involve a search that’s greedy. It can be as trivial as an agent A that encounters “Because A()=X” as an answer to “Why should I do X?”, which is clearly an irrelevant point to consider (pebblesorters don’t pursue primeness morally-because they are pebblesorters, even as they pursue it approximately causally-because they are pebblesorters).
Perhaps a reasoner should be bounded in an even stronger sense than limits on how hard it’s allowed to search, by instead working in an environment of carefully curated statements, with some epistemic membrane deciding which statements to channel (when) for further consideration. Anything else would expose the reasoner to its crash space, things it’s not ready to either see or willfully ignore (there’s chicken rule for ignoring claims about the current action, but there are other claims that might also need to be ignored, and it’s less clear how to do that).
(This is also my model of how pseudokindness could work, offering bespoke-curated options intended as not being from the crash space, without directly optimizing the patient.)
What happens if the exam is given either on Saturday at midnight minus epsilon or on Sunday at 00:00? Seems surprising generally and also surprising in different ways across reasoners of different abilities and precisions given the choice of epsilon.
EDIT: I think it’s also just as surprising if given at midnight minus epsilon on any day before Sunday, and therefore surprising any time. If days are discrete and there’s no time during the day for consideration then it falls back on the original paradox, although that raises the question of when the logical inference takes place. I think this could be extended to an N-discrete-days paradox for any non-oracle agent that has to spend some amount of time during the day reasoning.