Stability in random Boolean cellular automata on the integer lattice

F. MICHEL DEKKING, LEONARD VAN DRIEL AND ANNE FEYAbstract. We consider one-dimensional random boolean cellular au-tomata, i.e., the cells are identified with the integers from 1 to N. Thebehavior of the automaton is mainly determined by the support of therandom variable that selects one of the sixteen possible Boolean rules,independently for each cell. A cell is said to stabilize if it will not changeits state anymore after some time. We classify the one-dimensional ran-dom boolean automata according to the positivity of their probabilityof stabilization. Here is an example of a consequence of our results: ifthe support contains at least 5 rules, then asymptotically as N → ∞the probability of stabilization is positive, whereas there exist randomboolean cellular automata with 4 rules in their support for which thisprobability tends to 0.