Content deleted Content added
tweak wording |
Thumperward (talk | contribs) →Proof: condense |
||
Line 29:
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 is sure the other has agreed to the attack plan. Both generals will always be left wondering whether their last messenger got through.
== Proof ==
{{unsourced section|date=November 2019}}
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. 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.
A non-deterministic protocol with a potentially variable message count can be compared to an edge-labeled finite [[tree (graph theory)|tree]], where each node in the tree represents an explored example up to a specified point. A protocol that terminates before sending any messages is represented by a tree containing only a root node. The edges from a node to each child are labeled with the messages sent in order to reach the child state. Leaf nodes represent points at which the protocol terminates. Suppose there exists a non-deterministic protocol ''P'' which solves the Two Generals' Problem. Then, by a similar argument to the one used for fixed-length deterministic protocols above, ''P' '' must also solve the Two Generals' Problem, where the tree representing ''P' '' is obtained from that for ''P'' by removing all leaf nodes and the edges leading to them. Since ''P'' is finite, it then follows that the protocol that terminates before sending any messages would solve the problem. But clearly, it does not. Therefore, a nondeterministic protocol that solves the problem cannot exist.▼
▲A non-deterministic protocol with a potentially variable message count can be compared to an edge-labeled finite [[tree (graph theory)|tree]], where each node in the tree represents an explored example up to a specified point. A protocol that terminates before sending any messages is represented by a tree containing only a root node. The edges from a node to each child are labeled with the messages sent in order to reach the child state. Leaf nodes represent points at which the protocol terminates.
==Engineering approaches==
| |||