Density classification conjecture for the GKL, Kari traffic, and majority-traffic rules
Let a cellular automaton or probabilistic cellular automaton evolve configurations in the binary state space on the one-dimensional lattice . The GKL cellular automaton and Kari traffic cellular automaton are the rules described above, and the majority-traffic probabilistic cellular automaton has parameter . A model classifies the density if, for an independent initial configuration with density , its trajectories converge weakly to for and to for . Density classification conjecture. The GKL cellular automaton, the Kari traffic cellular automaton, and the majority-traffic probabilistic cellular automaton with
for some , classify the density. These rules are among the best-performing candidates for density classification on finite rings, but the asserted classification on the infinite lattice remains unproved in the source.
References
Primary source
Ana Busic, Nazim Fates, Jean Mairesse and Irene Marcovici, “Density classification on infinite lattices and trees”, arXiv:1111.4582 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.