Sometimes I feel the need to bridge the gap between the understanding of something, and the ability to explain it. I don't use formal language because (a) I probably don't know it, and (b) mostly, neither does the reader. Caveat lector, I am not a logician, I just play one on LiveJournal, and some of my favourite problems are knowledge puzzles. So, inspired by one of the interesting bits of paper stuck to my wall:
Possible worlds. It might be raining in New York. It might not. But I can know things about what we call "the world" without knowing whether it is raining in New York. There are (at least) two possible worlds, between which I cannot currently distinguish. In one of them, it is raining in New York, and in one, it is sunny. I don't know which of them is the "true" world. But I don't really need to! This is a part of how.
- (Implication; boring) Given a set of possible worlds, if we know a fact, say X about the current world, and in all worlds where X is true, Y is also true, then we know that Y is true. For example, if (X) it is raining here, then (Y) the streets are wet, irrespective of whether (Z) it is raining in New York. We have made a statement about X and Y without knowing Z, that is, without understanding the entire situation. We have partial knowledge. The definition of implication is built like this: In all possible worlds, Y or not X. (Can anyone remind me of the precise definition?)
- (Knowledge; more interesting) The knowledge of a participant Alice is a part of the state of the world. If Alice knows W, then we have a new fact X=(Alice knows W), and we can again derive facts Y which are common to all possible worlds where X is true. Now we are detectives; Alice knew he was dead. Therefore, Alice must have seen him murdered or been told. Lack of knowledge works just like knowledge in this respect. A sudoku example would be easier, but harder to represent in an LJ post. I'll come back to this case in a bit, to explain knowledge structures.
- (Recursive application; trickier) Hercule Poirot states, "I now know how did it." Now you and I, and the characters in the room all know that he knows who did it. But we don't know who did it. I am Alice; then A knows H knows X. But the possible values for X (and thus the worlds containing them) are still indistinguishable to A. Two definitions come from this:
- Everybody Knows:
- For a particular X, everybody knows X. That is, for any person A, A knows X.
- Common Knowledge:
- For a particular X, everybody knows X. Also, for any people A and B, A knows B knows X. But this last relation is infinitely defined: A knows B knows C knows D knows ..... knows X. This is very different from the Everybody Knows case, where A might not know that B knows X.
The simple solution of the Two Armies Problem requires the construction of Common Knowledge. As the Wikipedia page explains (in less formal language), Everybody Knows is established by the success of the first horseman, but it is not enough to coordinate an attack. Which do you use in your own work or software? Is it enough? Does it matter to you?
I want to explain the bit about Kripke structures and modal logic, and explain the solutions of some much harder puzzles, but perhaps today isn't the time. It's where a participant A can model the indistinguishable worlds of another participant B based on knowledge of B's knowledge, and thus derive information about the possible worlds based on invariants across that model. It might include source code. It will probably involve solutions to the hats problem, the muddy children problem and McCarthy's room problem.