Probing robustness of cellular automata through variations of asynchronous updating
- PDF / 1,136,474 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 95 Downloads / 170 Views
Probing robustness of cellular automata through variations of asynchronous updating Olivier Boure´ • Nazim Fate`s • Vincent Chevrier
Published online: 8 September 2012 Springer Science+Business Media B.V. 2012
Abstract Typically viewed as a deterministic model of spatial computing, cellular automata are here considered as a collective system subject to the noise inherent to natural computing. The classical updating scheme is replaced by stochastic versions which either randomly update cells or disrupt the cell-to-cell transmission of information. We then use the novel updating schemes to probe the behaviour of elementary cellular automata, and observe a wide variety of results. We study these behaviours in the scope of macroscopic statistical phenomena and microscopic analysis. Finally, we discuss the possibility to use updating schemes to probe the robustness of complex systems. Keywords Asynchronous cellular automata Robustness Discrete dynamical systems Phase transitions Directed percolation
1 Introduction Cellular automata (CA) are known as a model of computation based on the parallel evolution of cells according to their neighbourhood state. Originating from the study of self-replicating systems as introduced by von Neumann (1966), they are considered as an alternative to sequential computing models. Indeed, their spatially-extended and yet O. Boure´ (&) N. Fate`s V. Chevrier Universite´ de Lorraine—INRIA Nancy Grand-Est—LORIA, Nancy, France e-mail: [email protected] N. Fate`s e-mail: [email protected] V. Chevrier e-mail: [email protected]
simple structure make them a suitable model for parallel computing and simulations of natural phenomena. In their original form they are deterministic and synchronously evolved, that is, all components of the system are updated simultaneously. However, as natural computing supposes the use of non-classical methods involving a number of interacting components, the determinism of the model is somewhat incompatible with the presence of noise. This raises the question of the robustness of CA, that is, the stability of the behaviour despite external disturbances, such as an asynchronous update or errors in transitions or interactions between cells. This question was initially discussed by Ingerson and Buvel (1984) who ‘‘wanted to estimate how much of the behaviour of CA comes from synchronous modeling and how much is intrinsic to the iteration process’’. For that purpose, they questioned the perfect synchrony hypothesis by randomising the transition function of elementary cellular automata (ECA), and observed behavioural changes. From their observations they concluded that the updating scheme plays a fundamental role in the behaviour of the system. Since then, authors have tackled the question of whether CA are robust to non-synchronous updating, either by keeping the same individual rule or adding adapted constructs (Peper et al. 2002). For instance, Grilo and Correia (2011) investigated behaviour changes for asynchronous symmetric 2-player evolut
Data Loading...
