Exponential Convergence to Equilibrium in Cellular Automata Asymptotically Emulating Identity
Henryk Fukś
Department of Mathematics
Brock University
St. Catharines, Ontario L2S 3A1, Canada
hfuks@brocku.ca
José Manuel Gómez Soto
Unidad Académica de Matemáticas
Universidad Autónoma de Zacatecas
Calzada Solidaridad entronque Paseo a la Bufa, Zacatecas, Zac. Mexico
jmgomezgoo@gmail.com
Abstract
We consider the problem of finding the density of ones in a configuration obtained by n iterations of a given cellular automaton (CA) rule, starting from a disordered initial condition. While this problem is intractable in full generality for a general CA rule, we argue that for some sufficiently simple classes of rules it is possible to express the density in terms of elementary functions. Elementary CA rules (k=2, r=1) asymptotically emulating identity are one example of such a class, and density formulas have been previously obtained for several of them. We show how to obtain formulas for density for two further rules in this class, 160 and 168, and postulate likely expressions for density for eight other rules. Our results are valid for arbitrary initial density. Finally, we conjecture that the density of ones for CA rules asymptotically emulating identity always approaches the equilibrium point exponentially fast.
