Hi folks, Some of you may recall the Firing Squad Synchronization Problem. The problem is basically this: You have a linear array of cellular automata. Each automaton uses the same rule set, and transitions to the next state based on its current state and the states of its immediate neighbors. The ones on the ends know they're on the end and can take that fact into account when transitioning. The initial configuration has all of the automata in an "idle" state, and one of the end automata (the "general") is forced into a "start" state. The array them begins transitioning in unison. At some point, the entire array must transition into a "fire" state in simultaneously (having never entered that state prior to that point). Also, an automaton in the "idle" state must remain in the idle state as long as all of its immediate neighbors are also in the idle state. (This prevents the entire array from immediately transitioning to the "fire" state.) There is a fairly intuitive O(3n) solution to the problem, and it is easily shown that you cannot do better than 2n - 2 (since that's the fastest the array width information can propagate back to the starting general). I've implemented a simple javascript engine that shows my solutions along with the best known solutions: http://karzes.best.vwh.net/fsquad.html Just set the parameters under the "new" column, then click "reset" to load them and "start" to begin running. You can specify the number of rows to show (retain), either a number or else "all" for everything. The rule sets show the number of states in parentheses. The "tjk-slow" rule set is my O(3n) solution, but is included because I consider it to be the most intuitive solution (find the mid-point, then solve the two half-sized problems). The remaining solutions are all time-optimal (i.e., exactly 2n - 2 transitions). My "tjk-fast" solution uses 9 states. Balzer has a similar solution that uses 8 states, and Gerken has a similar solution that uses 7 states. The record holder is Mazoyer, with a 6-state solution which is interesting in that it not only uses fewer states, but also takes a fundamentally different approach: While the other solutions all find the mid-point, Mazoyer instead finds the point that is 2/3 of the way into the array. It has been shown that no 4-state solution exists, but it is unknown whether a 5-state solution is possible. Beware that if you specify too great a width (> 100 or so), Firefox becomes extremely slow when resetting the display (which is just an HTML table). There's no reason for it to be so slow, but I expect it's recalculating the displayed table over and over when it doesn't need to. IE doesn't appear to suffer from this performance bug. Tom