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 Z\mathbb{Z}. The GKL cellular automaton and Kari traffic cellular automaton are the rules described above, and the majority-traffic probabilistic cellular automaton has parameter α\alpha. A model classifies the density if, for an independent initial configuration with density pp, its trajectories converge weakly to 1Z1^{\mathbb{Z}} for p>1/2p>1/2 and to 0Z0^{\mathbb{Z}} for p<1/2p<1/2. Density classification conjecture. The GKL cellular automaton, the Kari traffic cellular automaton, and the majority-traffic probabilistic cellular automaton with

0<α<αc0<\alpha<\alpha_c

for some 0<αc1/20<\alpha_c\leq 1/2, 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

Never refreshed

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.