# Lambda the Ultimate

 100 prisoners and a light bulb started 12/14/2003; 6:51:37 AM - last post 12/18/2003; 12:08:15 PM
 Ehud Lamm - 100 prisoners and a light bulb   12/14/2003; 6:51:37 AM (reads: 8552, responses: 17)
 100 prisoners and a light bulb Yes, we have a fun department here on LtU. There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion? Would you have chosen Python, like this guy here, as the language of choice for playing with this puzzle? Posted to fun by Ehud Lamm on 12/14/03; 6:54:22 AM

 Marc Hamann - Re: 100 prisoners and a light bulb   12/14/2003; 10:08:48 AM (reads: 905, responses: 6)
 Are you sure this isn't a hoax problem? Let's switch this problem into computer terms: Given 100 data items in memory and a 1-bit register, create a process that chooses each of the data items at random from memory. This process can only toggle the register; it has no other storage. When all 100 data items have been chosen, call the exit routine. Or perhaps, we can make this a little bit simpler: Count to 100 using a 1-bit register. I would have to be a pretty dedicated Python fan to think it could help me with this one... ;-) (Addendum: having looked at his solution, the trick seems to be that there is hidden storage, the prisoners' memories, to make it work. But I think that is cheating. ;-) )
 Ehud Lamm - Re: 100 prisoners and a light bulb   12/14/2003; 10:12:27 AM (reads: 915, responses: 3)
 Read the paper... The prisoners, obviously, have their own memory, and have reasoning ability.
 Marc Hamann - Re: 100 prisoners and a light bulb   12/14/2003; 10:33:02 AM (reads: 909, responses: 2)
 The prisoners, obviously, have their own memory, and have reasoning ability Is this obvious? Compare this with a similar problem such as the Dining Philosophers. If we assume the philosophers have normal communicative abilities, the problem goes away, because they can simply negotiate a solution with their neighbour. But the point of the problem is to model a computational situation where this solution is not possible or adds further complexity of its own. A personal pet peeve: I think these kinds of problems should clearly state all of their assumptions. Relying on the hearer to decide what other facts are allowable or not brings in "human factors". ;-)
 Peter Van Roy - Re: 100 prisoners and a light bulb   12/14/2003; 10:33:03 AM (reads: 899, responses: 1)
 Would you have chosen Python, like this guy here, as the language of choice for playing with this puzzle? I would have chosen a constraint language like Oz or SICStus Prolog. See, e.g., the "Self-Referential Aptitude Test" in section 8.3 of the Mozart Finite Domain Tutorial for a good example of the kinds of weird problems that constraints can solve easily.
 andrew cooke - Re: 100 prisoners and a light bulb   12/14/2003; 5:03:26 PM (reads: 811, responses: 1)
 well, i'm glad you posted that. i was going to post something similar, but i decided it made me look too stupid ;o) the problem is that you read the question and assume that is all the state available. so immediately, you (i) think - this is carzy! impossible with so little state! but of course the other processes have state. nothing in the problem says otherwise. it is only the communication channel that is restricted. abstractions like the idea of state make life so much simpler for us, in so many cases, that we take it for granted that we can always apply the abstraction (in its obvious form). sometimes things are more complex. someone who knew nothing of computer science would not immediately discard this problem as insoluble. this is while i felt so stupid :o( have you heard the one about the surgeon that is so upset they cannot operate on a boy to save his life? the boy is the surgeon's son. yet the boy was injured in the same accident that killed his father...
 andrew cooke - Re: 100 prisoners and a light bulb   12/14/2003; 5:08:36 PM (reads: 818, responses: 1)
 I think these kinds of problems should clearly state all of their assumptions. if you'd only been born 25 years earlier. you could have solved the frame problem, prevented the ai winter, and we would all be happily using lisp!
 Ehud Lamm - Re: 100 prisoners and a light bulb   12/15/2003; 1:45:53 AM (reads: 735, responses: 0)
 Constraints are nice, but I don't really see how I would apply thme in this case. Anyone?
 bryan rasmussen - Re: 100 prisoners and a light bulb   12/15/2003; 2:24:01 AM (reads: 718, responses: 1)
 I am totally against hermaphroditic surgeons.
 andrew cooke - Re: 100 prisoners and a light bulb   12/15/2003; 2:31:07 AM (reads: 725, responses: 0)
 the solution given is extremely fragile. in a situation like that, it's quite likely that prisoners will become depressed, confused and possibly suicidal. an incorrect switching on - either accidental or not - would be disasterous. is there a more robust solution? or does a single bit of communication imply no possibility error correction?
 bryan rasmussen - Re: 100 prisoners and a light bulb   12/15/2003; 2:45:36 AM (reads: 719, responses: 0)
 although the time period is long, the period between each iteration is also long, thus prisoner resource usage is hopefully not great. The counter prisoner I'm sure saves a number at the end of each day, and looks at it just before going to the room. He is unlikely to make a mistake. Any prisoner that has never been in the room will definitely not think that they have been. Therefore the non counter prisoners are less fragile than the counter. Non-counters might get suicidal and decide to end it all, and all their comrades by saying that everyone has been in room. But I don't think that is calculable in the context of the problem.
 Marc Hamann - Re: 100 prisoners and a light bulb   12/15/2003; 4:39:40 PM (reads: 564, responses: 0)
 but i decided it made me look too stupid ;o) Boy, if I let that worry me, I'd never post in public. ;-) Even when I think I have a solid case, there is always someone who thinks it is dumb... ;-)
 Marc Hamann - Re: 100 prisoners and a light bulb   12/15/2003; 4:46:01 PM (reads: 578, responses: 0)
 if you'd only been born 25 years earlier. you could have solved the frame problem, prevented the ai winter, and we would all be happily using lisp! Well, I don't know about the Lisp part, but it has seemed rather obvious to me for a long time that if the AI gang had paid a little more attention to the great logicians of the early 20th century (in both their sucesses and failure), they wouldn't have been so sanguine about HAL 9000 being just around the corner. ;-)
 Michael Feathers - Re: 100 prisoners and a light bulb   12/15/2003; 8:35:23 PM (reads: 537, responses: 0)
 The answer is... each prisoner should listen for the others' footsteps and count how many have visited the living room. The problem doesn't mention using a computer or a programming language. Michael (also takes apart Rubik's cubes and puts them together again)
 Christopher Hendrie - Re: 100 prisoners and a light bulb   12/16/2003; 7:41:33 AM (reads: 493, responses: 0)
 To address Ehud's question about which languages we'd choose to use, I vote for a higher-order formulation in Haskell/ML/Scheme, a bit like the stream-processors example from the Arrows paper: ```type Bulb = Bool type Step = Int type Prisoner = Step -> Bulb -> Action data Action = Announce | Continue Bulb Prisoner``` Prisoner behaviours can be specified concisely and cleanly, and when prisoners change roles, they just modulate to a different prisoner function. In Haskell, you get the benefit that it's impossible to write a solution which accidentally cheats -- the type system enforces the rules of the prison (modulo unsafePerformIO).
 Darius Bacon - Re: 100 prisoners and a light bulb   12/17/2003; 9:46:26 PM (reads: 371, responses: 0)
 Making it impossible to cheat suggests doing it in E, about like this (no actual solution here, just the skeleton): ```# Return true iff the prisoners built by makePrisoner successfully # solve the puzzle. def puzzle(makePrisoner :Frozen, rng) :boolean { # A list of 100 prisoners def prisoners := map(def _(_) :any { makePrisoner() }, 1..100) # The light bulb var bulbOn := false def bulb { to isOn() :boolean { bulbOn } to toggle() :void { bulbOn := !bulbOn } } # Set of prisoners not yet taken to the room var unselected := prisoners.asSet() while (true) { # Pick a random prisoner. def prisoner := rng.pick(prisoners) unselected := unselected.remove(prisoner) # Have them visit the lightbulb and tell whether they think we're done.' if (callWithOneShot(prisoner, bulb)) { return unselected.isEmpty() } } } # Return fn(argument), but supplying a one-use proxy instead of the # argument directly. Revoking the proxy corresponds to taking the # prisoner back to their cell. def callWithOneShot(fn, argument) :any { def [proxy, revoker] := makeRevoker(argument) def result := fn(proxy) revoker.revoke("Attempt to reuse one-shot argument") result }```
 Christopher Hendrie - Re: 100 prisoners and a light bulb   12/18/2003; 7:12:58 AM (reads: 356, responses: 0)
 Interesting approach! I take it the :Frozen attribute prevents makePrisoner from creating closures with shared state? I ended up considering a similar approach to extend my Haskell framework. While implementing some experimental prisoners, I started using (functional) arrays for internal state. It occured to me that it would be more efficient to allow prisoners to keep their state in the ST monad (for fast array update), but then the ST type 'leaks' out into the type of the prisoner, and if used naively could allow the prisoners to share a covert channel. It occured to me to use rank-2 polymorphism, just as in runST. If the run_prison function requires a list of polymorphic (in the state token) make_prisoner functions, then the generated prisoners cannot communicate, even if they are all threaded into the same ST monad. There have been some interesting recent papers exploring the relationships between cryptographic/capability security and parametric polymorphism -- it's neat to see it come up again in a concrete context.
 Darius Bacon - Re: 100 prisoners and a light bulb   12/18/2003; 12:08:15 PM (reads: 340, responses: 0)
 Yes, that's what Frozen was supposed to mean, though I didn't get it quite right. I meant for Frozen to certify that makePrisoner has no references to mutable state; makePrisoner() could then create new mutable state and return it, but it would have no place to stick away state to be shared in the next call. That should have been DeepFrozen instead -- a Frozen object could still have immutable references to other objects that are themselves mutable. Also, I haven't tested this code. :) I'd be interested in the Haskell with rank-2 polymorphism -- sounds fancier than anything I've done in that language yet.