Skip to Main content Skip to Navigation
New interface
Conference papers

Probabilistic initial value problem for cellular automaton rule 172

Abstract : 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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 2:16:49 PM
Last modification on : Tuesday, March 7, 2017 - 3:06:51 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:20:59 AM


Publisher files allowed on an open archive




Henryk Fuks. Probabilistic initial value problem for cellular automaton rule 172. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. pp.29-40, ⟨10.46298/dmtcs.2761⟩. ⟨hal-01185497⟩



Record views


Files downloads