Lost in translation: a critical view of epistemic puzzles solutions.

Computational Logic SeminarTuesday, March 5, 20132:00 pmGraduate Center, room 3209

Sergei Artemov

Lost in translation: a critical view of epistemic puzzles solutions.

The CUNY Graduate Center

There are two basic ways to specify an epistemic scenario:
1. Syntactic: a verbal description with some epistemic logic on the background and some additional formalizable assumptions; think of the Muddy Children puzzle.
2. Semantic: providing an epistemic model; think of Aumann structures – a typical way to define epistemic components of games.

Such classical examples as Muddy Children, Wise Men, Wise Girls, etc., are given by syntactic descriptions (type 1), each of which is “automatically” replaced by a simple finite model (type 2). Validity of such translations from (1) to (2) will be the subject of our study.

We argue that in reducing (1) to (2), it is imperative to check whether (1) is complete with respect to (2)  without which solutions of puzzles by model reasoning in (2) are not complete, at best. We have already shown that such reductions can be justified in the Muddy Children puzzle MC due to its model categoricity: we have proved that MC has the unique “cube” model Q_n for each n. This fixes an obvious gap in the “textbook” solution of Muddy Children which did not provide a sufficient justification for using Q_n.

We also show that an adequate reduction of (1) to (2) is rather a lucky exception, which makes the requirement to check the completeness of (1) w.r.t. (2) necessary. To make this point, we provide a simplified version of Muddy Children (by dropping the assumption “no kid knows whether he is muddy”) which admits the usual deductive solution by reasoning from the syntactic description, but which cannot be reduced to any finite model.

Professor Artemov holds a Distinguished Professor position at the Graduate Center of the City University of New York, in the Computer Science, Mathematics and Philosophy programs. He is also Professor of Mathematics at Moscow State University, the founder and the Head of the research laboratory Logical Problems in Computer Science. He conducts research in the areas of logic in computer science, mathematical logic and proof theory, knowledge representation and artificial intelligence, automated deduction and verification and optimal control and hybrid systems.

Posted by on February 21st, 2013