Non-deterministic density classification with diffusive probabilistic cellular automata

Abstract

We present a probabilistic cellular automaton (CA) with two absorbing states which performs classification of binary strings in a non-deterministic sense. In a system evolving under this CA rule, empty sites become occupied with a probability proportional to the number of occupied sites in the neighborhood, while occupied sites become empty with a probability proportional to the number of empty sites in the neighborhood. The probability that all sites become eventually occupied is equal to the density of occupied sites in the initial string.

4 pages, 4 figures

Cited by in corpus (5)

• Probabilistic cellular automata with conserved quantities
• A Comprehensive Taxonomy of Cellular Automata
• Towards the Probabilistic Earth-System Model
• Strictly local one-dimensional topological quantum error correction with symmetry-constrained cellular automata
• Density Classification with Non-Unitary Quantum Cellular Automata