The Unexpected Hanging Paradox has been described as follows:
A judge tells a condemned prisoner that he will be hanged at noon on one weekday in the following week but that the execution will be a surprise to the prisoner. He will not know the day of the hanging until the executioner knocks on his cell door at noon that day.
Having reflected on his sentence, the prisoner draws the conclusion that he will escape from the hanging. His reasoning is in several parts. He begins by concluding that the "surprise hanging" can't be on Friday, as if he hasn't been hanged by Thursday, there is only one day left - and so it won't be a surprise if he's hanged on Friday. Since the judge's sentence stipulated that the hanging would be a surprise to him, he concludes it cannot occur on Friday.
He then reasons that the surprise hanging cannot be on Thursday either, because Friday has already been eliminated and if he hasn't been hanged by Wednesday noon, the hanging must occur on Thursday, making a Thursday hanging not a surprise either. By similar reasoning, he concludes that the hanging can also not occur on Wednesday, Tuesday or Monday. Joyfully he retires to his cell confident that the hanging will not occur at all.
The next week, the executioner knocks on the prisoner's door at noon on Wednesday — which, despite all the above, was an utter surprise to him. Everything the judge said came true.
I first heard this paradox years ago, but only now do I think that I can provide a satisfactory account. I guess some people won't see this as a deeply challenging problem though, as it's quite clear that the word "unexpected" is under-defined. For example, it could mean unexpected based on the information that you have at the start or unexpected based on the information you have on a particular day or unexpected based on the day of the hanging.
We'll consider different definitions of unexpected, which involves considering different definitions of expectected. We'll define E* as expected based on the information that you have at the start, which we'll further clarify as meaning that you are able to determine that it must be on a particular day. Clearly, no day is expected based on definition E*, which mean that a hanging any day would be unexpected based on this information. Call this definition of unexpected U*.
Next, we'll define E1 to mean expected based on the information you have on a day excluding the judge's statement. On Friday, an execution will count as expected according to this definition and an execution on any other day will count as unexpected. As before we can create a definition of unexpected, U1, from E1. We do this by excluding the day that is expected according to E1. The hanging will therefore be unexpected according to U1 if it occurs according to this definition between Monday and Thursday.
Next, we define E2 to mean expected based on the information you have on a day, interpreting the judge's statement to mean that the hanging is unexpected according to U1. The hanging occurring on Friday would be in contradiction with knowing that the hanging would unexpected according to definition U1. If the hanging occurs on Thurday, you'll know that it'll occur that day as it can't occur on Friday. Again, we define U2 from E2, but this time, in addition to excluding any day where a hanging would be expected by E2, we exclude any day where the hanging would be inconsistent with the interpretation of the judge's statement used by E2. According to this definition, the hanging will be unexpected if it occurs between Monday and Wednesday.
We can continue on in this vein. E3 is defined by taking the judge to be asserting U2, which means that the hanging can't occur on Thursday or Friday without being inconsistent with the judge's statement; and can't occur on Wednesday without the prisoner being able to figure it out on Wednesday. The hanging meets the defintion of U3 if it occurs on Monday or Tuesday. We then get E4 from U3 and U4 occurs on Monday. Then E5 from U4 and U5 doesn't occur on any day.
We can even create a chart demonstrating for each day whether the test would be unexpected if it occurred on that day:
Cells with U represent days where a hanging would be unexpected according to that definition. E represents a day where a hanging would be correctly expected on that day - there can only be one such day otherwise the prisoner would have been mistaken. I represents a day that is inconsistent with the judge's statement.
Each EN was defined in terms of U(N-1). The prisoner interprets the judge to be envisioning a notion of expected E$ such that if the hanging occurs on day D, it is unexpected if the prisoner couldn't determine on day D that it it was going to occur on day D given the knowledge that the hanging will be unexpected according to U$. Here U$ consisted of any day not expected according to E$ nor inconsistent with how E$ interpreted the judge's statement.
Such a notion would indeed have the property that if L is the last possible day according to notion E$, that the prisoner would know on day L that the hanging would occur on that day since if it occurred on any later day it would meet notion E$. The "paradox" provided by the prisoner simply proves an impossibility result.
In my books, this is a much more satisfying solution than simply noting that the word "unexpected" is underdefined. Instead, we've mapped out the possibility space of such definitions and shown that the prisoner's desire for a reflective definition can't be met, but instead that there is inevitably some "precession" instead.