Article Preview
TopProposed as a computational model describing a replicating machine (Neumann, 1966), cellular automata (CAs) are both computational and mathematical objects that have been used as simulation models in many phenomena related to biology, physics and social sciences (Green, 1990; Smith, 1994). The structure of a cellular automaton relies on a set of cells organized as a d-dimensional regular grid, each cell being able to take on one of the states from a finite set. As a discrete dynamical system, the values of the cells change when applying their transition function (or rule) to their neighborhood, defined by the cell itself and its local vicinity, and the result of applying the function for a finite time leads to its temporal evolution (Sarkar, 2000).
The set of possible rules is a discrete space defined by all rules sharing the same characterization. A rule defines the dynamical behavior of a cellular automaton, and for each one, its typical dynamics can be obtained. Among the possible rules of each space, to delimit those of interest to simulations of some phenomena or that present a target dynamical behavior is a difficult task due to the number of possible rules in each space, which increase exponentially with the number of cells in the neighborhood. To make things worse, in general it is not possible to predict the future state of the CA without applying the rule for an arbitrary time. The possible initial configurations make the possibility by predicting the future state of the system even more difficult.
The initial configuration of the system is the configuration of its cell states. In the case of 3 states and configurations of 83 cells, for instance, there are 383 possible initial configurations, and not necessarily all of them results would yield the same dynamics. However, for most of the possible initial configurations the application of a specific rule results in typical behavior, so that the classification of the dynamical behavior of a rule always relies on the associated typical behavior of its temporal dynamics. Naturally, not all initial configurations lead to the typical behavior of the rule, which can lead to errors. It is then necessary to generate a representative set to derive the typical dynamical behavior of a rule (Wolfram, 2002).