Topology-induced phase transitions in totalistic cellular automata (Q1948107)

This article deals with totalistic cellular automata (CA) over random tesselations: each cell of the plane holds a binary state that evolves according to a local rule which only depends on the number of neighboring cells with state 1. It responds to other results attributing the property of sensitivity (to initial conditions) to some of these CA without emphasizing the tesselation over which it is considered, though it plays a crucial role. Indeed, the authors show the results of their numerical experiments computing the maximal Lyapunov exponent (which basically corresponds to the maximal long-range communication speed) of many CA over random tesselations with prescribed mean connectivity (average number of neighbors): 89 so-called intrinsically complex CA have a positive exponent which always remains the same or evolves smoothly with respect to the connectivity, while 124 so-called topology-mediated complex CA involve a phase transition: a slight change in the mean connectivity can suddenly bring a positive Lyapunov exponent to 0.