Discrete Mathematics & Theoretical Computer Science |

- 1 Department of Mathematics and Statistics [St. Catharines]

We present a method of solving of the probabilistic initial value problem for cellular automata (CA) using CA rule 172 as an example. For a disordered initial condition on an infinite lattice, we derive exact expressions for the density of ones at arbitrary time step. In order to do this, we analyze topological structure of preimage trees of finite strings of length 3. Level sets of these trees can be enumerated directly using classical combinatorial methods, yielding expressions for the number of $n$-step preimages of all strings of length 3, and, subsequently, probabilities of occurrence of these strings in a configuration obtained from the initial one after $n$ iterations of rule 172. The density of ones can be expressed in terms of Fibonacci numbers, while expressions for probabilities of other strings involve Lucas numbers. Applicability of this method to other CA rules is briefly discussed.

Source: HAL:hal-01185497v1

Volume: DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS

Section: Proceedings

Published on: January 1, 2010

Imported on: January 31, 2017

Keywords: cellular automata,initial value problem,preimage trees,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

This page has been seen 286 times.

This article's PDF has been downloaded 194 times.