|
===For deterministic protocols with a fixed number of messages===
Because this protocol is '''[[Deterministic_system|deterministic]]''', suppose there is a '''sequence''' of a fixed number of messages, one or more successfully delivered and one or more not. The assumption is that there should be a ''shared certainty for both generals to attack''.
Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least (presumably the receiver) would decide not to attack. {{Citation needed|reason=There is probably an error in the proof. In original reference or only here? See Talk page for details.|date=May 2017}} From the viewpoint of the sender of that last message, however, the '''sequence''' of messages sent and delivered is exactly the same as it would have been, had that message been delivered.
Since the protocol is '''deterministic''', the general sending that last message will still decide to attack.
We've now created a situation where the suggested protocol leads one general to attack and the other not to attack—contradicting the assumption that the protocol was a solution to the problem.
===For nondeterministic and variable-length protocols===
A '''nondeterministic''' protocol with a variable message count can be compared to a '''finite''' [[tree (graph theory)|tree]], where each leaf or branch (node) in the tree represents an explored example up to a specified point.
The roots of this tree are labeled with the possible starting messages, and the branch nodes stemming from these roots are labeled with the possible next messages. Leaf nodes represent examples which end after sending the last message. A protocol that terminates before sending any messages is represented by a null tree.
Suppose there exists a '''nondeterministic''' protocol which solves the problem. Then, by a similar argument to the '''deterministic''' example in the previous section, where a deterministic protocol can be obtained from the non-deterministic one by removing all leaf nodes, the '''deterministic''' protocol must then also solve the problem.
Since the '''nondeterministic''' protocol is '''finite''', it then follows that the protocol represented by the empty tree would solve the problem. Clearly this is not possible. Therefore a '''nondeterministic''' protocol which solves the problem cannot exist.<ref>{{cite book|last1=Kennard|first1=Fredrick|title=Thought Experiments: Popular Thought Experiments in Philosophy, Physics, Ethics, Computer Science & Mathematics|publisher=Lulu.com|isbn=9781329003422|page=346|url=https://books.google.nl/books?id=sX-pCQAAQBAJ|accessdate=15 September 2015}}</ref>
===Proof by symmetry===
| 