The "Unexpected Hanging Paradox" is a situation in which a prediction is successfully made, even though a logical proof indicates that it couldn't possibly happen.
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 "Two Generals Problem" is a situation in which two generals agree on a time to attack when the only means of communication is unreliable (i.e. a message might not get through), even though a logical proof indicates that it can't possibly be done.
The Two Generals' Problem was the first computer communication problem to be proved to be unsolvable.
…
The first general may start by sending a message "Attack at 0900 on August 4." However, once dispatched, the first general has no idea whether or not the messenger got through. This uncertainty may lead the first general to hesitate to attack due to the risk of being the sole attacker.To be sure, the second general may send a confirmation back to the first: "I received your message and will attack at 0900 on August 4." However, the messenger carrying the confirmation could face capture and the second general may hesitate, knowing that the first might hold back without the confirmation.
Further confirmations may seem like a solution—let the first general send a second confirmation: "I received your confirmation of the planned attack at 0900 on August 4." However, this new messenger from the first general is liable to be captured, too. Thus it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general be sure the other has agreed to the attack plan. Both generals will always be left wondering whether their last messenger got through.
In theory, the logical conclusions are that the prisoner cannot be surprised and that the generals cannot confirm the time.
But in practice, it is quite the opposite.
The prisoner really is surprised when he is hanged on Wednesday.
And if even only a few messages get through, the Generals can agree on a time. Each message is numbered, and is resent (with the same ID number) if acknowledgement is not received within a predetermined time. Additional messages are sent at regular intervals up until the time of the attack, but only after the previous message has been acknowledged.
- #G1-1: "attack at 0900 on August 4"
- #G2-1: "got your #1"
- #G1-2: "got your #1. carry on" [message lost]
- #G1-2: "got your #1. carry on"
- #G2-2: "got your #2. carry on"
- …
- #G1-9: "got your #8. today's the day"
- #G2-9: "got your #9. see you soon"
- …
The logical proof's "Both generals will always be left wondering whether their last messenger got through." is still true, but it is also irrelevant. It isn't the last message that's important, it's the first message.
Long before the 9th messages are sent, each General already knows, with certainty, that both Generals have seen message #G1-1. If that message had not been received by the second General, none of the other messages would have existed. But they do.
Just before the time of the attack, both Generals know that they have each seen the message, and know that it is appropriate for them to attack. There is no uncertainty.
The only time this problem is "impossible to solve" is when all further messages are cut off, as would happen if the enemy had detected the other army and destroyed it. But that's a problem of prematurely terminated communication, not of intermittently unreliable transmission.
The "Unexpected Hanging" and the "Two Generals" are very similar situations.
In each case:
- the logical reasoning is about resolving incomplete knowledge.
- the proofs start at the critical point (the execution deadline and the first message).
- one starts with certainty and propagates it backward through time to to prove there is no uncertainty, and the other starts with uncertainty and propagates it forward through time to prove that there is no certainty.
- the infinite chain of reasoning is terminated by a secondary event (the sentencing and the attack).
- at the time of the secondary event, correct decisions can be made, and everything resolves as it should.
In each case, the confusion is with the given proofs of impossibility, not with the procedures for how to surprise the prisoner or how to confirm the knowledge of information.
In each case, the methods of proof fail in identical ways.
Despite their many similarities, I have never seen these two problems discussed together.
The logical "proofs" are nearly identical in nature, and both fail to match reality for the same reason.
So, Why is one considered an example of a "complex paradox", and the other an example of a "simple unsolvable problem"?
You are missing the point of the two generals paradox.
It is not hard to find a threshold at which each general knows the attack time. As soon as the first message is received, this is true.
It is not hard to find a threshold at which each general knows that each general knows the attack time. As soon as the second message is received, this is true.
It is not hard to find a threshold at which each general knows that the $99^{\text{th}}$ message has been received. As soon as the $100^{\text{th}}$ message is received, this is true.
The actual impossibility is different. No matter how the generals make their decisions, one of the following two alternatives must hold:
If neither general is willing to tolerate outcome 1, then what it's impossible to do is to find a threshold at which each general knows that the other general is willing to attack.
At the end of the day, when the generals have exchanged some number of messages and we've reached the attack time, the generals must follow a rule such as "If I've received at least $k$ confirmation messages, I will attack; otherwise, I will not." (Of course, we can allow $k=0$ "I will always attack" or $k=\infty$ "I will never attack".) If you don't specify such a rule, then you haven't specified when the generals will act and when they won't.
Suppose that for the first general, $k=100$. Then the second general is put into an awkward position when sending back the $100^{\text{th}}$ confirmation and getting no response.
This is true of any threshold (for either general). So there is no threshold that either general can use to guarantee that neither general attacks alone, except for the $k=\infty$ threshold of never attacking.
You are of course free to propose other strategies for the generals to follow. They can be as silly as "attack iff you've received an odd number of confirmation messages" or something smarter and more elaborate. But the same proof works as long as your strategy is specific enough to answer the question "Will the generals attack if $k$ messages have been exchanged?" for each value of $k$.
Or, to put it differently: consider any example you like of a "successful" communication between the two generals: one after which they decide to attack at the end. Let's say that in this communication, $N$ messages are exchanged. ($N$ can be as large as you like, but of course it is finite.)
Now consider situations $S_0, S_1, S_2, \dots, S_N$ where situation $S_k$ is defined as follows: the first $k$ messages get through exactly as in the successful example, then afterwards no messages get through. In particular, in $S_0$, no messages get through at all.
In situation $S_0$, the generals both don't attack. In situation $S_N$, they both do. That means there must be some point at which a change happens. Either there's a case in which some general attacks alone, or there's a sudden switch at some $k$: in situation $S_{k-1}$, neither general attacks, and in situation $S_k$, both generals attack.
But that's impossible! Situation $S_{k-1}$ and $S_k$ are identical from the point of view of one general: the first general, if $k$ is odd, and the second general, if $k$ is even. That general can't decide to attack in situation $S_k$ but not $S_{k-1}$.