Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Science

Solving Feynman's Unsolved Puzzle? 90

Posted by Cliff from the here's-one-for-your-brain dept.
An anonymous reader asks: "In The Feynman Lectures on Computation, Richard Feynman poses an interesting little puzzle involving the synchronization of finite state machines acting as generals and soldiers. While he was able to find an answer to the problem, the minimum time solution apparently eluded him, and he ended his description of the puzzle with the following Fermat-like declaration: 'Somebody has actually found a solution with this minimum time. That is very difficult though, and you should not be so ambitious. It is a nice problem, however, and I often spend time on airplanes trying to figure it out. I haven't cracked it yet.' My best attempt performs at about 3N, not quite the minimum time of 2N-2. So I'm asking Slashdot: Has anyone ever come across the minimum time solution to this puzzle? Or maybe someone here can figure it out!"

"Here is the full description of the problem, in Feynman's own words. Please remember that these are finite state machines, so you can't use any methods that involve counting the number of soldiers or assigning a number to each soldier.

Problem 3.4: Before turning to Turing machines, I will introduce you to a nice FSM problem that you might like to think about. It is called the 'Firing Squad' problem. We have an arbitrarily long line of identical finite state machines that I call 'soldiers'. Let us say there are N of them. At one end of the line is a 'general', another FSM. Here is what happens. The general shouts 'Fire'. The puzzle is to get all of the soldiers to fire simultaneously, in the shortest possible time, subject to the following constraints: firstly, time goes in units; secondly, the state of each FSM at time T+1 can only depend on the state of its next-door neighbors at time T; thirdly, the method you come up with must be independent of N, the number of soldiers. At the beginning, each FSM is quiescent. Then the general spits out a pulse, 'fire', and this acts as an input for the soldier immediately next to him. This soldier reacts as in some way, enters a new state, and this in turn affects the soldier next to him and so on down the line. All the soldiers interact in some way, yack yack yack, and at some point they become synchronized and spit out a pulse representing their 'firing'. (The general, incidentally, does nothing on his own initiative after starting things off.)

There are different ways of doing this, and the time between the general issuing his order and the soldiers firing is usually found to be between 3N and 8N. It is possible to prove that the soldiers cannot fire earlier than T=2N-2 since there would not be enough time for all the required information to move around. Somebody has actually found a solution with this minimum time. That is very difficult though, and you should not be so ambitious. It is a nice problem, however, and I often spend time on airplanes trying to figure it out. I haven't cracked it yet."
This discussion has been archived. No new comments can be posted.

Solving Feynman's Unsolved Puzzle? More

Solving Feynman's Unsolved Puzzle?

Comments Filter:
  • Is this what people refer to as the slashdot effect!

  • I'm no math wiz (Score:2, Insightful)

    by iq in binary ( 305246 )
    Define a straight line.....

    Seriously, the straight line might just be the solution to that problem.

    That thought just popped up in my head, feel free to flame me for being open.

  • A new kind of science (Score:5, Interesting)

    by Anonymous Coward on Friday December 13, 2002 @09:03AM (#4879775)
    Stephen Wolfram's "A New Kind of Science" addresses this puzzle with cellular automata. I remember hearing about it at a lecture at CMU. If my memory serves me right, he has found a solution and it is contained inside his book. You might try looking there.
    • As I drink more caffiene-laiden mud (That's how I like my coffee), I seem to recall hearing about a couple of College students from Kansas solving this problem.

      I don't have a link handy, and I'm too tired to google. Anybody else recall the same?
    • What's the difference between cellular automata and finite state machines? Isn't the former just a whole bunch of the latter?

      • As I understand it (someone correct me if I'm wrong), cellular automata have an FSM at their heart. Their inputs are determined spatially -- eg. their neighbors outputs serve as inputs. Also, I believe the output of cellular automata's FSM is generally of the form "alive" or "dead". Think, for instance, of Conway's "Life", or the various "Rule XX" that Wolfram examined that lead to him writing ANKOS.

        So, in other words, cellular automata are a bunch of specialized FSMs.

        More arbitrary FSMs can take more arbitrary inputs and produce more arbitrary outputs (or sets of outputs).

        --Joe
        • I did my Bachelor's Thesis on cellular automata and how they can be used to model physical systems. While it's true that any cell's neighbors can provide inputs to a cell's finite state machine, the "output states" can be anything. You aren't limited to a cell being "alive" or "dead." In many CA programs, a given cell's state is often represented by color.

          I've seen many 3- and 4-state CA systems that have been simulated. I've also seen many CA systems with widely divergent definitions of what a "neighbor" is. (The most common cases are where the neighbor is a cell adjacent on one of the four cardinal directions, or where the neighbor is a cell on one of the eight adjacent squares. This assumes a rectilinear or chessboard space.)

          Another error in your description is the statement that cellular automata are a bunch of specialized finite state machines. This implies that each cell could be running a different "program." The truth is, most if not all CA systems run the same "program" on every cell, in lockstep. In other words, cellular automata are a special case of SIMD processing. (I suppose it's possible to construct a MIMD example of CA, but then you run into the problem of how you assign your initial conditions -- i.e., not only do you need to assign an initial state to each cell, but you also need to assign a "program" to each cell.)

          • Thanks for the clarifications! I guess from your description, the Feynman's FSM Firing Squad can be considered a 1-D array of cellular automata, correct?

            BTW, by "specialized", I meant that the notion of FSM embodied in a cellular automata is specialized over the more general notion of a state machine -- that is, cellular automata are a specialized form of FSM. I didn't mean to imply by the word "specialized" that different cells have different programs--although, you could provide for that in a single program by providing disconnected subsets of the states in your single "program" (which also solves the "MIMD initialization problem" you mention offhand).

            Here's an example of what I mean by disconnected subsets. Suppose each cell has 6 states labelled A through F. Suppose A, B and C all have rules for transitioning among A, B and C. Similarly, suppose D, E, F have rules for transitioning among D, E and F. You can't reach A, B, or C if you start in D, E, or F, and vice-versa. If all your cells have programs of this form, then which subprogram a given cell 'runs' depends only on which subset of the allowed statespace you allocate that cell's starting state from.

            --Joe
        • More concisely, CA are a limited group of identical FSMs whos inputs are the current states of their spatial neighbors.
        • (someone correct me if I'm wrong)

          This is Slashdot. You don't have to write that part.

    • Stephen Wolfram's "A New Kind of Science" addresses this puzzle with cellular automata.

      Cellular automata are exactly what this problem is asking about! A CA is a bunch of FSMs hooked together. More precisely, a quick Googling says: [herts.ac.uk]

      On a regular lattice (repeated structure of points have the same kind of neighborhood) one puts a finite-state machine at each point. The input to the machine is the states of all machines in its neighborhood. The behaviour is to change its state based in a determined way, as a function of the states of its neighbors and its own state. The states of all machines in the lattice are updated synchronously (simultaneously).
      • CAs don't have to consist of finite-state automata. Still, the question posed by Feynman is definitely relevant to CAs, since each automaton is identical in function.

        The solution is indeed reproduced in Wolfram's book, which I will excerpt in a separate reply if it has not already been quoted.
      • The input to the machine is the states of all machines in it's neighborhood
        Dos that mean a topological neighborhood? If not that sounds vague.

  • An optimum solution ... (Score:3, Informative)

    by Xner ( 96363 ) on Friday December 13, 2002 @09:29AM (#4879876) Homepage
    A certain "A. Walkman" claims to have found the optimum solution in 1966, and published it in "Information and Control":

    Waksman, A. An optimum solution to the firing squad synchronization problem. Information and Control 9 (1966), 66--78.

    Unfortunately, the article does not seem to be available online.
    If anyone decides to take a quick trip down to the library, I would be delighted if they could share the answer.

  • The prisoners and the light bulb (which I can't quite remember).
    Where the prisoners get released after each one has switched the light on.
    You get a best of 2n-2 for this
    2n for switching on and off and -2 because of the first and last prisoner.

    The worst case could be infinate.
    • If you don't know the puzzle in question (i didn't), here it is:
      100 Prisoners and a Light Bulb There are 100 prisoners, each kept in their own isolated cell. Each day one prisoner is chosen at random and taken into a central room where there is a light. The light is either ON or OFF. The prisoner may view the light and turn it on or off if they like, before being returned to their cell. The prisoner may also guess that all the prisoners have been into the exercise room at some time so far. If they are right then all go free. If they are wrong then everyone is shot. The prisoners are allowed to confer before being imprisoned, but may not communicate once in prison. (You may assume that the light starts OFF) Can you find an algorithm which garauntees release of the prisoners eventually? How many days do you expect to wait for the prisoners to be released? Find an algorithm which has the smallest number of expected days until the prisoners are released. Do this for every possible number of prisoners.
      Thanks to procrastinating.org [procrastinating.org]
      • The best solution I can come up with is this - grouping days into batches of 100

        If prisoner X has entered the room previously on this batch of days, he switches the light on. After the 100th day, if the light is off, the prisoner states that all people have entered the room. Otherwise turn the light off.

        This is arather inefficient thouygh. It relies on all 100 prisoners being randomly selected once in a batch of 100 days. We could probable find some optimisations to this solution though.
      • The way the problem is worded, it's impossible to come up with an expected number of days.

        To quote, "Each day one prisoner is chosen at random [...]"
        If the same prisoner happened to be chosen at random EVERY TIME then the prisoners would never be released. Now, the odds of that happening to infinity are 0, but there is a chance that it could happen until the maximum age of the prisoners. It's even more likely that every prisoner gets randomly selected except for one, until they all die.

        To make it possible, we have to assume that each prisoner will only be picked again after every other prisoner has. Perhaps we just shuffle the prisoners into a random order, and loop it. But then the prisoner can just wait until selected again, and then he'll know. Unless we assume that they're all selected before looping back, but that the prisoners don't know that.

        Is that last condition necessary for solving the problem without making it trivial, or did I make a mistake somewhere?

  • Solutions (Score:4, Informative)

    by Anonymous Coward on Friday December 13, 2002 @09:34AM (#4879902)
    http://xraysgi.ims.uconn.edu/fsquad/firing-solutio n.html [uconn.edu]

  • probably wrong (Score:1, Interesting)

    by kix ( 24024 )
    well, I am quite sure, that this is the wrong answer, since it is way too simple, but could anybody explain, what exactly is wrong with it:

    ok, as the thing said, first all soldiers are in a default do-nothing state, then the first gets the fire! message, with a counter 0, then increments the counter and passes it to the next soldier and goes to the "wait-reply" state. then the next soldier does the same thing and so on, until the end of the line. now, when the last soldier recieves the message - fire, counter is x, it goes to the state "fire after x time ticks", decrements x and passes it on, the next one (since it is in the wait-reply state, it knows to go into this state) recieves the counter, goes into "fire after x ticks", decrements x and passes it on, until we reach the first soldier, who immediately fires (since x is zero), as do all the others, since their counters run out at the same time..

    and since the message passes the line twice, it should take N-2 ticks, assuming we start counting from the time the first soldier gets the message..

    • Re:probably wrong (Score:4, Informative)

      by dmorin ( 25609 ) <dmorin@@@gmail...com> on Friday December 13, 2002 @09:49AM (#4879968) Homepage Journal
      Finite state machines are not allowed to have counters, or do conditional logic (you need a Turing machine for that). At least, that is a condition I understood to be correct in the problem. Otherwise you're right, it is a little easy.
      • So does this mean I also can't do something like "switch to state C if N-1 and N+1 are both in state B, and N is in state A?"

        How does an FSM work then? Can we only trigger a change based on a change?
        • Think of it as a table that gives an output state at time t+1 as a function of the input states at time t.

        • Re:Conditional logic (Score:4, Insightful)

          by dmorin ( 25609 ) <dmorin@@@gmail...com> on Friday December 13, 2002 @10:14AM (#4880108) Homepage Journal
          You can do conditional logic in FSM's (my statement was a little too broad), you just have to plan it out ahead of time. Base it on what you know. The only communication you have with N-1 or N+1 is the pulse they send you. As far as I know, an FSM isn't even allowed to have a state called "Waiting for pulse" which then turns into a "If pulse is type 1 go here, else go here" node. Instead you have to put yourself into "Waiting for pulse type 2" state, and then when a pulse comes in, you have toa ssume that's what you got. So you have to know ahead of time what state to put yourself in, you can't be surprised by anything.

          This is why this is such a good problem -- because a giant FSM has the overlying assumption that there are no unknowns, but the problem definition seems to have an unknown in N. It's not really unknown once the system is running, though. The problem is just to build the smaller pieces in such a way that when stuck together, they work correctly regardless of what N is. That's different from saying "they work correctly *because* they know what N is, or can otherwise predict it."

          • Re:Conditional logic (Score:1, Informative)

            by Anonymous Coward
            A FSM is simply a function which statically maps input state to output state. The reason why this is called pulse or signal is that obviously the state of a FSM can only change if one of its inputs change, thus change can cause further change, which is what you expect from a pulse or signal, but no change can not cause change: A FSM cannot "act" spontaneously.
          • I'm still personally a little confused about this.

            When I've programmed with FSMs, I've always thought of them as graphs of states (points) and transitions (edges). An input (message pulse, word, signal, whatever) then can trigger a state change, which I've usually implemented via some kind of table. The state change is accomplished by a function; in a useful program the state transition could call an arbitrary list of functions that might involve sending other messages to other state machines, etc., or doing other "stuff" with arbitrary side effects, but as far as the state machine is concerned, you would always just move to either a different state or the same state again.

            So I need a little more info to crack this: to pin down some definitions. Just how restrictive are the rules of this little universe?

            - Can each soldier have a DIFFERENT state machine?

            - Obviously the state machine consists of states and transitions. What I'm hearing from dmorin is that my soldier can't distinguish between different messages. In other words, when it gets a "hut!" message it always moves on to the next state. It can't distinguish between hearing the general shout "fire" and some other message like "put your gun away and go home."

            - Time is passing in discrete intervals, say, seconds, but can the "tick" of some global clock also be a message? or is the only message each soldier can hear just the generic "hut!" message from the general at one end or the soldiers on either side?

            - Maybe this is needlessly picky, but would "firing" count as a state? The way I usually think of state machines, "fire" would be what happened when the state machine got a message that triggered the transition between "waiting to fire" and "fired." And "speaking" (issuing a "hut!" message to the soldier on the left and right would also be a transition.

            - Lastly, can the soldier "aim" (distinguish) which soldier he yells "hut!" to? Or will both the soldier on the left and right "hear" him?

            Paul

            • Re:Conditional logic (Score:1, Informative)

              by Anonymous Coward

              - Can each soldier have a DIFFERENT state machine?

              No. This isn't really a restriction, because you could simply encode the different state machines on different subsets of the state set.

              - Obviously the state machine consists of states and transitions. What I'm hearing from dmorin is that my soldier can't distinguish between different messages. In other words, when it gets a "hut!" message it always moves on to the next state. It can't distinguish between hearing the general shout "fire" and some other message like "put your gun away and go home."

              The soldier looks at his own state and the states of his direct neighbors and then chooses his next state. The "messages" are state changes of neighbors. You can also code it so that a single soldier oscillates: *a*->b, *b*->c (* for arbitrary states of the neighbors).

              - Time is passing in discrete intervals, say, seconds, but can the "tick" of some global clock also be a message? or is the only message each soldier can hear just the generic "hut!" message from the general at one end or the soldiers on either side?

              There is no central time information or counter. All FSMs decide on their next state at the same time, based on their current state. If the soldiers need to wait a certain number of time intervals, they have to count themselves.

              - Maybe this is needlessly picky, but would "firing" count as a state? The way I usually think of state machines, "fire" would be what happened when the state machine got a message that triggered the transition between "waiting to fire" and "fired." And "speaking" (issuing a "hut!" message to the soldier on the left and right would also be a transition.

              Firing in this context is when an FSM enters a special state. The task is to create the FSM so that all instances enter one state at the same time and no instance enters this state before that.

              - Lastly, can the soldier "aim" (distinguish) which soldier he yells "hut!" to? Or will both the soldier on the left and right "hear" him?

              If you want to think of it in communication terms: At each time intervall, every soldier tells his direct neighbors his own state. That's it.

            • To answer your questions:

              Each soldier can view the state of its two adjacent neighbors, and then those states are used to look in the transition table to determine the soldier's state for the next time step.

              Time's only effect is to cause the system to advance to the next time step; i.e., at a clock tick, each soldier examines the state of its two neighbors, looks up the proper transition in its transition table, and changes state accordingly.

              Yes, "fire" is a state, and is generally regarded as required to be a unique state. Transitions have no effect on neighbors until the next clock tick (when the neighbors examine their neighbors' states), so "speaking" isn't a transition. Technically, "speaking" doesn't even occur.

              The soldiers to the left and right of a particular soldier are the only ones who can examine the state of that soldier. They do so only at a clock tick.

              Hope this helps!
        • I think I get the idea.

          So am I corrent if I say my above example is a valid state transition?
      • Finite state machines are indeed allowed to have counters, as long as the counters are of finite capacity. (The result is that the FSM becomes incredibly large as it expands to hold enough state/transition information for all the non-counter states times the counter capacity.)

    • The problem with this is that these are finitestate machines, and the problem stated that the solution cannot depend on N. So to implement a counter in a FSM you need at least as many states as the number you need to count to. This means your FSMs change depending on N.
    • well, I am quite sure, that this is the wrong answer...the first gets the fire! message, with a counter...

      A quote from the article:

      Please remember that these are finite state machines, so you can't use any methods that involve counting
    • That was my impression too.

      As for finite states, well you can turn this into a state table if you want to (a large number of states to be sure, but not a very large number of bits) but you can only cope with a finite number of soldiers.

      http://xraysgi.ims.uconn.edu/fsquad/firing-solut io n.html

      Having read the state tables for the alleged solutions I am clueless as to how they're supposed to work. A synopsis of the strategy being adopted would be very helpful.

      It seems to me that the initial message to fire MUST take N ticks to propagate to the Nth soldier. The message that the final soldier has been located MUST take N ticks to propagate back to the first soldier. Hence a theoretical limit of 2N + some number.

      Exactly how you store the intermediate information ("wait, you'll get another message soon!") is really just a technical detail for folks who want to program a formal finite state machine (I think they live near people with infinitely long spools of tape) which can't store integers. The rest of us would use your (or a similar) solution and get on with our lives.
    • well, I am quite sure, that this is the wrong answer, since it is way too simple, but could anybody explain, what exactly is wrong with it:

      Actually, your solution would be quite correct if you knew in advance the maximum number of soldiers that are allowed.

      Contrary to what others have said, you can implement counters and conditional logic in FSMs, but in order for it to be a finite state machine, you must specify in the design of the FSM exactly how many states there are as well as the transition rules. Now each possible value for a counter is a separate state, so they must be enumerated in advance. Your soldiers would have 2k+1 states where k is the maximum value allowed for the counter. There is the initial wait state, plus k states after recieving the first message and waiting to pass it along to the next soldier, plus k decrement states.

      Now, the total number of soldiers must be finite, but unlimited. If you design your soldiers with k counter states, what if there are k+1 soldiers? Then your solution would fail.

      So, if the problem were modified so that the maximum possible number of soldiers were specified in advance, then your solution would be a correct minimum-time solution. But if no such maximum is specified, then the solution must be more complicated.

  • Surely You're Joking (Score:3, Funny)

    by Tuxinatorium ( 463682 ) on Friday December 13, 2002 @09:48AM (#4879960) Homepage
    Mr. Feynman!
  • That chick from Stephenson's "Diamond Age". What the hell was her name again? Seems like this would be right up her alley.

    :)

  • Solutions (Score:5, Informative)

    by cdrudge ( 68377 ) on Friday December 13, 2002 @10:07AM (#4880064) Homepage
    For those people wondering about what the 3n solution is, here is a page that describes it: Firing Squad Solution [uconn.edu]. A decent diagram as to the firing order is here [uconn.edu]. The page also links [uconn.edu] to a description about the 2N-2 solution, but claims that it is buggy and only works in certian Ns, not for all values of N.

  • Links to several solutions (Score:5, Informative)

    by Linux_ho ( 205887 ) on Friday December 13, 2002 @11:05AM (#4880447) Homepage
    Can be found on this page [uconn.edu]

  • I have a solution... (Score:4, Funny)

    by i_am_nitrogen ( 524475 ) on Friday December 13, 2002 @11:13AM (#4880504) Homepage Journal
    But unfortunately it is too large to be contained in this margin.

  • Wow! (Score:3, Funny)

    by Hubert_Shrump ( 256081 ) <cobranet@@@gmail...com> on Friday December 13, 2002 @01:33PM (#4881777) Journal
    I didn't know we could also ask Slashdot stuff that may not even have an answer! This is awesome!

    Do you feel the community, people? Because I am totally feeling it right now.

    There are so many things I'd like to know...

    (waits for the inevitible)

  • Feeling short (Score:4, Funny)

    by redtail1 ( 603986 ) on Friday December 13, 2002 @03:04PM (#4882543)
    To loosely paraphrase Douglas Adams, I love listening to the sound of stories like these as they whoosh over my head.
  • realistically - the general would of course broadcast his order and all soldiers would immediately fire upon hearing the order, so total time til fire would be 1+ execution time, assuming that all soldiers could hear the general and also implying that the speed of sound is not considered a factor.

    in fact, their would be absolutely no way to get a simple state machine to function in this manner, or to fire simultaniously, as it would have either a 0(no function or no action) or a 1(action) state, theirfor the general would be 0 at start, then would change to 1 for fire. the first soldier would then fire as he went to state 1, as a simple state machine has no logic to decide to "fire" or to "pass it on". so by this reasoning, the total time to have all soldiers fire would be N+1, N for the number of soldiers as the second soldier would of coarse fire as a result of the first soldier fireing and etc, and the general would have a time of 1 to give the order.

    N+1.

    now if the soldiers had logic to decide to "ass it on" AND memory and logic to calculate time decimation and N, then 2N-2 would be the only functional solution. this also assumes that not only the general, but the last soldier have different capabilities from the rest of the soldiers, as the last solider must calculate the total and also know to reverse the movement of data back towards the general.
    • as it would have either a 0(no function or no action) or a 1(action) state,

      Why do you assume that there are only two states in the state machine?

      N+1, N for the number of soldiers as the second soldier would of coarse fire as a result of the first soldier fireing and etc, and the general would have a time of 1 to give the order.

      The problem stipulates that all fire at the same time.

      now if the soldiers had logic to decide to "ass it on" AND memory and logic to calculate time decimation and N, then 2N-2

      FSMs only have if-then relationships. They don't have any "memory" to store anything, they only tell you what the next state is going to be based on some input. Nothing about the FSM changes during runtime, thus they can't store arbitrary values.

      Also, I don't follow your logic for saying 2N-2 would be the only solution. Do you actually understand the problem?

Slashdot Top Deals

Get hold of portable property. -- Charles Dickens, "Great Expectations"

Close