Hans van Ditmarsch

Barteld Kooi

A group of 100 prisoners, all together in the prison dining area, are told that they will be all put in isolation cells and then will be interrogated one by one in a room containing a light with an on/off switch. The prisoners may communicate with one another by toggling the light switch (and that is the only way in which they can communicate). The light is initially switched off. There is no fixed order of interrogation, or interval between interrogations, and the same prisoner may be interrogated again at any stage. When interrogated, a prisoner can either do nothing, or toggle the light switch, or announce that all prisoners have been interrogated. If that announcement is true, the prisoners will (all) be set free, but if it is false, they will all be executed. While still in the dining room, and before the prisoners go to their isolation cells (forever), can the prisoners agree on a protocol that will set them free? At first glance, this riddle may seem impossible to solve: how can all of the necessary information be transmitted by the prisoners using only a single light bulb? There is indeed a solution, however, and it can be found by reasoning about knowledge. This book provides a guided tour through eleven classic logic puzzles that are engaging and challenging and often surprising in their solutions. These riddles revolve around the characters’ declarations of knowledge, ignorance, and the appearance that they are contradicting themselves in some way. Each chapter focuses on one puzzle, which the authors break down in order to guide the reader toward the solution. For general readers and students with little technical knowledge of mathematics, One Hundred Prisoners and a Light Bulb will be an accessible and fun introduction to epistemic logic. Additionally, more advanced students and their teachers will find it to be a valuable reference text for introductory course work and further study.

One Hundred Prisoners and a Light Bulb

Jerome Lang

Shier Ju

Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this book constitutes the refereed proceedings of the Third International Workshop on Logic, Rationality, and Interaction, LORI 2011, held in Guangzhou, China, in October 2011. The 25 revised full papers presented together with 12 posters were carefully reviewed and selected from 52 submissions. Among the topics covered are semantic models for knowledge, for belief, and for uncertainty; dynamic logics of knowledge, information flow, and action; logical analysis of the structure of games; belief revision, belief merging; logics and preferences, compact preference representation; logics of intentions, plans, and goals; logics of probability and uncertainty; logical approaches to decision making and planning; argument systems and their role in interaction; norms, normative interaction, and normative multiagent systems; and logical and computational approaches to social choice.

Third International Workshop, LORI 2011, Guangzhou, China, October 10-13, 2011. Proceedings

Logic, Rationality, and Interaction

Wiebe van der Hoek

Dynamic Epistemic Logic is the logic of knowledge change. This book provides various logics to support such formal specifications, including proof systems. Concrete examples and epistemic puzzles enliven the exposition. The book also offers exercises with answers. It is suitable for graduate courses in logic. Many examples, exercises, and thorough completeness proofs and expressivity results are included. A companion web page offers slides for lecturers and exams for further practice.

Hans van Ditmarsch

About

Books

Join the club