Density classification conjecture for the GKL, Kari traffic, and majority-traffic rules

At least 14 years old · documented by

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<αc≤1/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.

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

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.