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."

Comments

A new kind of science

[Anonymous Coward]

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.

probably wrong

[kix]

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..