Periodic solutions of one-dimensional cellular automata with random rules

arXiv1909.06913MaRDI QIDQ6325347FDOQ6325347

Authors: Janko Gravner, Xiaochen Liu 

Publication date: 15 September 2019

Abstract: We study cellular automata with randomly selected rules. Our setting are two-neighbor rules with a large number $n$ of states. The main quantity we analyze is the asymptotic probability, as $noinfty$, that the random rule has a periodic solution with given spatial and temporal periods. We prove that this limiting probability is non-trivial when the spatial and temporal periods are confined to a finite range. The main tool we use is the Chen-Stein method for Poisson approximation. The limiting probability distribution of the smallest temporal period for a given spatial period is deduced as a corollary and relevant empirical simulations are presented.

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

This page was built for publication: Periodic solutions of one-dimensional cellular automata with random rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325347)