Skip to Main content Skip to Navigation
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 metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185497
Contributor : Coordination Episciences Iam <>
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

File

dmAL0103.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185497, version 1

Collections

Citation

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. ⟨hal-01185497⟩

Share

Metrics

Record views

567

Files downloads

428