Predictability in cellular automata

PLoS One. 2014 Oct 1;9(10):e108177. doi: 10.1371/journal.pone.0108177. eCollection 2014.

Abstract

Modelled as finite homogeneous Markov chains, probabilistic cellular automata with local transition probabilities in (0, 1) always posses a stationary distribution. This result alone is not very helpful when it comes to predicting the final configuration; one needs also a formula connecting the probabilities in the stationary distribution to some intrinsic feature of the lattice configuration. Previous results on the asynchronous cellular automata have showed that such feature really exists. It is the number of zero-one borders within the automaton's binary configuration. An exponential formula in the number of zero-one borders has been proved for the 1-D, 2-D and 3-D asynchronous automata with neighborhood three, five and seven, respectively. We perform computer experiments on a synchronous cellular automaton to check whether the empirical distribution obeys also that theoretical formula. The numerical results indicate a perfect fit for neighbourhood three and five, which opens the way for a rigorous proof of the formula in this new, synchronous case.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Cell Biology*
  • Models, Biological*

Grants and funding

Funding provided by AA PNII-ID-PCCE-2011-0015, Romanian National Authority for Scientific Research, http://uefiscdi.gov.ro/, AA Grant PNII-TE-320, Romanian National Authority for Scientific Research, http://uefiscdi.gov.ro/ and CC Grant PNII-TE-320, Romanian National Authority for Scientific Research, http://uefiscdi.gov.ro/. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.