Rapport de Recherche RR2008-12: Directed Percolation arising in Stochastic Cellular Automata Analysis

Abstract. Cellular automata are both seen as a model of computation and as tools to model real life systems. Historically they were studied under synchronous dynamics where all the cells of the system are up-dated at each time step. Meanwhile the question of probabilistic dy-namics emerges: on the one hand, to develop cellular automata which are capable of reliable computation even when some random errors oc-cur [24,14,13]; on the other hand, because synchronous dynamics is not a reasonable assumption to simulate real life systems. Among cellular automata a specific class was largely studied in syn-chronous dynamics: the elementary cellular automata (ECA). These are the "simplest " cellular automata. Nevertheless they exhibit complex behaviors and even Turing universality. Several studies [20,7,8,5] have focused on this class under α-asynchronous dynamics where each cell has a probability α to be updated independently. It has been shown that some of these cellular automata exhibit interesting behavior such as phase transition when the asynchronicity rate α varies. Due to their richness of behavior, probabilistic cellular automata are also very hard to study. Almost nothing is known of their behavior [20]. Understanding these "simple " rules is a key step to analyze more complex systems. We present here a coupling between oriented percolation and ECA 178 and confirms observations made in [5] that percolation may arise in cellular automata. As a consequence this coupling shows that there is a positive probability that the ECA 178 does not reach a stable configuration with positive probability as soon as the initial configuration is not a stable configuration and α> 0.996. Experimentally, this result seems to stay true as soon as α> αc ≈ 0.5.