Density classification conjecture for the GKL, Kari traffic, and majority-traffic rules
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.