One hundred prisoners and a lightbulb — logic and computation


This is a case-study in knowledge representation. We analyze the ‘one hundred prisoners and a lightbulb’ puzzle. In this puzzle it is relevant what the agents (prisoners) know, how their knowledge changes due to observations, and how they affect the state of the world by changing facts, i.e., by their actions. These actions depend on the history of previous actions and observations. Part of its interest is that all actions are local, i.e. not publicly observable, and part of the problem is therefore how to disseminate local results to other agents, and make them global. The various solutions to the puzzle are presented as protocols (iterated functions from agent’s local states, and histories of actions, to actions). The computational aspect is about average runtime termination under conditions of random (‘fair’) scheduling



    Upload a copy of this work     Papers currently archived: 89,446

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

Similar books and articles

Verifying one hundred prisoners and a lightbulb.Hans van Ditmarsch & Jan van Eijck - 2010 - Journal of Applied Non-Classical Logics 20 (3):173-191.
Descriptions of game actions.Hans P. van Ditmarsch - 2002 - Journal of Logic, Language and Information 11 (3):349-365.
Puerto Rican Political Prisoners.Jan Susler - 2000 - Radical Philosophy Review 3 (1):28-40.
Medicine in handcuffs: restraining prisoners and detainees undergoing medical treatment and hospitalisation.Noam Lubell - 2003 - Tel-Aviv: Physicians for Human Rights-Israel. Edited by Ruchama Marton, Michal Bar-Or & Johanne Malka-Shalom.


Added to PP

27 (#499,487)

6 months
1 (#1,005,371)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Jan Van Eijck
University of Amsterdam