2012/12/13 by Li Ning, Liang Shi-li, Ning, Li +7
Physics and Astronomy · #Adaptation and Self-Organizing Systems (nlin.AO) #Cellular Automata and Lattice Gases (nlin.CG) #FOS: Physical sciences #nlin.AO #nlin.CG
paper · pdf · doi:10.48550/arxiv.1212.3069
8 pages, 6 figures
arxiv created 2012/12/13 · arxiv updated 2012/12/14
In this paper, we present a 4-state solution to the Firing Squad Synchronization Problem (FSSP) based on hybrid rule 60/102 Cellular Automata(CA). This solution solves the problem on the line of length 2n with two generals. Previous work on FSSP for 4-state systems focused mostly on linear cellular automata, where synchronizes an infinite number of lines but not all possible lines. We give time-optimal solutions to synchronize an infinite number of lines by rule 60 and rule 102 respectively, and construct a hybrid rule 60 and 102 states transition table. Compared to the known solutions of cellular automata, the hybrid CA way is simpler and faster, the minimal time is (n-1) step.