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."
Is this what people refer to as the slashdot effect!
For problems, seek only the simplest solution, complexity brings with it more problems.
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.
Define the General (or trigger var?), then.
As I said, I'm no math wiz, haven't any credits under my name past Mat121 (College Algebra, being interested in calc based phys that'll change). But it seems that problem like these are solved not by the math, but the logic.
That's one of the great things about being young and dumb like me, everything is open to interpretation.
Of all the Universal Constants, here's one I know: Nice guys finish last
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
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..
I am SO cool I can keep meat fresh for a WEEK!!!!
Mr. Feynman!
Repeal the DMCA!
This link includes everything the poster wanted to know, including the 1966 Waksman solution from "Information and Control", and an even "more efficient" one that uses less states.
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?
:)
www.HearMySoulSpeak.com
first solder yells out 0, next yells out 1, ... etc.. to N-1... and letting t = their number. At the end, each soldier yells, fire in t, back down the line. Effectively each soldier stores his own countdown on the first pass at the count, when the count comes back his way, he knows to fire in t seconds. This syncs them and solves it in 2n-1 (I think...). How's that?
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.
Pathman, Free (as in GPL) 3D Pac Man
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.
I think I get the idea.
So am I corrent if I say my above example is a valid state transition?
Nell, dammit... ;-)
How can you dare not remembering Princess Nell?
the computer is online
i am not at it
what a waste of ressources
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 tried with a N=8 set. I don't fully understand what a FSM 'can do', based on what I thought it meant, all of them fired in T=14. Which is coincidentally 2N-2.
Can anyone give a link to what exactly a FSM is? I don't really understand what they can react to. I had set it up almost 'conditional', but based on a table that listed all possible "pulse" types from both directions. Like if at T=0 N1 and N3 are both "pulse type 6", then at T=1 N2 emits "pulse type 7" and so on...
Why not put the general in the middle of the line of soldiers (ie - N becomes 2 lines of N/2)?
Come on you humorless (or clueless) moderators. Mod this man up!
Simple rule
the state of your neighbors change your state if they are 1 and you can only see the state of your neighbour fomr the time before (says so in the rules)
therefore when teh general yiells fire
the first soldier turns into a 1
=1000
the second second unit 1 is still 1 and unit 2 since unit 1 was at 1 in second 1 turns into 1
=1100
the rest is logic try to follow it with these
=0110
=1011
=1001
=1111
4 soldiers 6 secs 2n-2
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.
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.
http://www.xdr.com/dash/feynman.html
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.
That was my impression too.
t io n.html
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-solu
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.
All night tonight I'm going to dream that this will be on the test. I'll tell you all if I wake up with an optimal solution.
Within those constraints.
Alas, I was not able to come up with the optimal solution.
I FAIL IT!
r*1+a*7
important proof here
Quit Slashdot Today!
the wrong space deletes me!
curse my clicky keyboard!
Quit Slashdot Today!
IQ in binary is on the right track. Nowhere does Feynman say that the line must be straight. Even if you assume that the line is in 1 dimensional space, the solution can be an N dimensional mapping. So, for example, the soldiers might be on the surface of a cylinder, so that the general is next to both ends of the line, simultaneously. If we scale up to N dimensions, then the general can be next to all soldiers simultaneously. Thus, the problem is solved with the minimal time lag of 1 tick of the clock. This means that the solutions that we have seen, are simply the most efficient mappings of N dimensions to 1 dimension. -Bruce I I tried logging in, but slashdot crashed Mozilla 1.2.1
Duh. After the general gives the order to fire, the first soldier fires in the first time period. In the second time period, the second soldier fires. In that same time period, the second, the first soldier fires again. Each soldier fires in succession. Each soldier keeps firing in every time period. When the the last soldier fires, all the soldiers will be firing simultaneously. Thus, the answer is N.