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."
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.
Of all the Universal Constants, here's one I know: Nice guys finish last
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.
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
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.
thank God the internet isn't a human right.
http://xraysgi.ims.uconn.edu/fsquad/firing-solutio n.html
Pathman, Free (as in GPL) 3D Pac Man
Mr. Feynman!
Repeal the DMCA!
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
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.
Spencer Ogden
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.
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."
www.HearMySoulSpeak.com
Can be found on this page
include $sig;
1;
But unfortunately it is too large to be contained in this margin.
A solution to the problem with music today
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.)
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)
Keep your packets off my GNU/Girlfriend!
To loosely paraphrase Douglas Adams, I love listening to the sound of stories like these as they whoosh over my head.
Reread the problem. The solution has to be independant of N. The same "soldier" should work wether there is 100 or 1000 or them. Thus you can't have a counter dependant on N. BTW where do you go that you don't study FSMs in digital logic, or design classes?
Why, o why must the sky fall when I've learned to fly?
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?
Why, o why must the sky fall when I've learned to fly?
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.
If I can be modded down for being a troll, can I be modded up for being an orc, or a balrog?