« Retrocausality in a Simple Optical Experiment? | Main | Mars Helicopter “Ingenuity” Almost Ready to Deploy »
Wednesday, March 31, 2021
TRACKING WITH CLOSEUPS: Cellular Automata: The Firing Squad Synchronisation Problem
This is a classic one-dimensional cellular automata problem which was posed by John Myhill and 1957 and solved by artificial intelligence pioneers John McCarthy and Marvin Minsky in a paper published in 1962. The original solution uses just three states, with each cell observing only its two immediate neighbours (with special rules for end cells with no neighbours), running in 3n time, where n is the number of cells.
The best known solution, found in 1987, runs in the optimal 2n−2 time with six states. It has been proved that no four state solution is possible, but it is unknown whether a five state solution exists.
Here is more on the firing squad synchronisation problem. I should add this as an example in Cellular Automata Laboratory.
Posted at March 31, 2021 10:24