Slashdot Mirror
Solving Feynman's Unsolved Puzzle?
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."
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.
Pathman, Free (as in GPL) 3D Pac Man
http://xraysgi.ims.uconn.edu/fsquad/firing-solutio n.html
Pathman, Free (as in GPL) 3D Pac Man
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.
www.HearMySoulSpeak.com
For those people wondering about what the 3n solution is, here is a page that describes it: Firing Squad Solution. A decent diagram as to the firing order is here. The page also links 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.
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.
Can be found on this page
include $sig;
1;
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.)
- 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.