Unexpected Execution Paradox

A fiend is caught and waits on death row. On a Monday morning his last avenue of appeal is exhausted, and the prison warden goes to give him the news:

Well, it's a bad end you've come to, and you richly deserve it. In fact this is still too good for the likes of you. To make it worse, to draw it out and make you sweat, I'll promise you this: we're going to come for you one morning before next Sunday, we're going to strap you in old sparky and we're going to watch you fry like a lambchop. But I'm not going to say just which morning it will be. It's going to be a complete surprise!

The fiend chuckles deep in his throat, a sound to freeze the warden's blood. He fixes him with his beady eyes like a butterfly under glass, and says:

Ha ha, copper, that hasty promise means you can't execute me at all! When I'm not busy in my day job as a fiend, I moonlight as a ComputerScientist! I know my way around the GeneralHaltingProblem, and here's what I have to say to you: if you come to halt me on the Saturday, the last day before Sunday, then I'll know there's nothing else you could do - it won't be any surprise at all. So that means you can't halt me on Saturday. But, that also means you can't do me on Friday, because, since Saturday is definitely out, if you wait till Friday I'll sure expect it then. Now since Friday and Saturday are out, it follows by the same reasoning that Thursday is out. And so on. Ha ha, copper, you just promised to keep me breathing forever!

Nevertheless, when they came for him on Wednesday, it was just as the warden promised, a complete surprise.

Obviously the convict had forgotten the GeneralHaltingProblemProblem.

This 'paradox' is simply playing with two different interpretations of what a 'complete surprise' means. The warden uses this concept to mean that "the convict will not be able to predict on which day they will come for him". The convict relaxes this interpretation to "when they will come, I will not be expecting them". Those interpretations seem to agree with each other, but they don't. The main difference is that the convict thinks he is allowed to expect the warden on more than one day, whereas the warden intend him to pick only one day.

To see this, let's analyze the convict's argument. For Saturday, his argument is correct. For Friday however, his argument only works if he is allowed to "expect them" for two days in a row. If he expects them Friday, then they can't come that day or it won't be a surprise. If he is then allowed to expect them again Saturday, then they can't come then either. However this is ridiculous: if he is allowed to be "expect them" many times then he could simply observe constant vigilance and they would never come. This is obviously not what the warden meant.

If we only give the convict one magic scroll-of-expectation which would protect him all day long against an equally magic scroll-of-lambchop, then the convict cannot be certain to use his scroll on the right day. On Friday morning, he cannot count Saturday out: if he uses his scroll Friday then it is possible that the warden will choose to burn him Saturday, and if he saves it for Saturday then it is possible that the warden will choose to burn him Friday. It is only Saturday morning that he can know for sure that they will come this day, and it might be too late.

Unless the warden has himself more than one scroll-of-lambchop, I don't think he can be certain to surprise the convict either, though. But most importantly, how is this 'paradox' related to the GeneralHaltingProblem?

Regrettably, an example of the general playing with words that makes dealing with graduate school types so difficult. -- AnonymousCoward and grad school dropout.

I have to disagree with the above analysis. The paradox holds even if there is only one day available for the execution.

It does? Please explain. Let's see if I can figure it out first... If there is only one day, then I think it is fairly easy to know which day the warden will come, so it won't be a surprise. So the convict knows that they will not come, but surprise!, they come anyway. Okay... is that really all there is to the paradox? They tell him "we will come on the day on which you think we will not come". But then if he thinks they will come on one particular day, then in fact he will think they will not come on that particular day, which in turn implies... Brilliant! Ah... and I was so damn sure of my first interpretation!

And now I can even see the faint link with the HaltingProblem:

ConvicP is a program. A very successful program. People give him loads of money for his services, for he alone can tell whether your program halts or not. Alas, ConvicP is not a true halting tester. Turing knows his secret and wants to expose it to the world. So he builds the scroll-of-lambchop, a very simple counter-example program which, as he explains to ConvicP, "will come to a halt on the day on which you think it will not come to a halt". It is impossible for ConvicP to make an accurate prediction, so he is exposed, arrested and eventually put on death row or something.

See BattleOfWits