One hundred prisoners and a lightbulb — logic and computation
AbstractThis 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
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.
The Gamut of Dynamic Logics.Martin Stokhof & Jan van Eijck - 2006 - In Dov Gabbay & John Woods (eds.), The Handbook of the History of Logic. Volume 6: Logic and Modalities in the Twentieth Century. Elsevier. pp. 499-600.
On Agents That Have the Ability to Choose.Wiebe van der Hoek, Bernd van Linder & John-Jules Meyer - 2000 - Studia Logica 66 (1):79-119.
On Agents That Have the Ability to Choose.Wiebe van Der Hoek, Bernd Van Linder & John-Jules Meyer - 2000 - Studia Logica 66 (1):79 - 119.
Categorically Rational Preferences and the Structure of Morality.Duncan MacIntosh - 1998 - In Peter Danielson (ed.), Modeling Rationality, Morality and Evolution; Vancouver Studies in Cognitive Science, Volume 7. Oxford University Press.
Medicine in Handcuffs: Restraining Prisoners and Detainees Undergoing Medical Treatment and Hospitalisation.Noam Lubell - 2003 - Physicians for Human Rights-Israel.
Maximization, Stability of Decision, and Actions in Accordance with Reason.Jordan Howard Sobel - 1990 - Philosophy of Science 57 (1):60-77.
Added to PP
Historical graph of downloads
Citations of this work
Hidden Protocols: Modifying Our Expectations in an Evolving World.Hans van Ditmarsch, Sujata Ghosh, Rineke Verbrugge & Yanjing Wang - 2014 - Artificial Intelligence 208 (1):18--40.