Ardeshir and Ramezanian: "A solution to the surprise exam paradox in constructive mathematics" (2012)

The surprise examination problem concerns a teacher who announces the following:

One of the next five days, you will have an exam; and I will pick the day of the exam such that when it comes, it will come as a surprise.

The problem with this announcement, according to one line of reasoning, is that it is in fact impossible to satisfy:

The teacher can't rationally place the exam on Friday, because it would then be completely predictable given that it hadn't occurred Monday through Thursday; but the teacher also can't place it on Thursday, because it would then be completely predictable given that it hadn't occurred Monday through Wednesday, and that the teacher will be rational on Friday; and similarly, it can't take place on Wednesday, etc. In this way, we end up concluding that the exam can't take place at all.

This impossibility argument rests on a number of assumptions: For instance, if the teacher is not guaranteed to be rational in the future, the argument collapses, just as in the case of the centipede game. Another assumption is that the teacher can only use pure (deterministic) strategies, a restriction that rules out the solutions to many games, including rock-paper-scissors.

Backwards Induction in Constructive Mathematics

However, the approach taken in the paper by Mohammad Ardeshir and Rasoul Ramezanian is to deny constructive validity of the argument above. They do so by translating the teacher's choice of examination day into a bounded and increasing series whose maximum identifies the day of the exam.

For instance, if the exam takes place on Thursday, the students might observe the following series:

1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, …

Since this series can is increasing and only takes values among the number {1, 2, 3, 4, 5}, it has a maximum according to classical reasoning. However, in constructive mathematics, this maximum is said not to exist because we can't explicitly identify which of the five numbers it is.

Given this translation, the teacher can now truthfully say:

I can construct a bounded and increasing series with values in {1, 2, 3, 4, 5} such that you cannot constructively infer its maximum from any finite segment.

That's doable; the standards of existence imposed by constructive mathematics are so high that as long as you haven't observed a 5 anywhere in the sequence, you have no constructively valid conclusion about the maximum. So even if the exam is placed on Friday, there is no specific natural number k such that you can with certainty infer the maximum of the series after having observed k items.

In other words, the students have no reliable algorithm for inferring what day the exam will be held. This conclusion does, however, rest crucially on the assumption that there can be arbitrarily large time lags between the jumps in the sequence.

Infinite Input Turing Machines

Towards the end of the paper, the authors introduce something called "Type 2 Turing machines." These are machines that can take infinite inputs and produce infinite outputs.

The reference they give for this concept is a textbook by Klaus Weihrauch. I will have to take a look at that at some point.