Problem 11

How are cellular automata affected by noise and other imperfections?

Many mathematical approaches to the analysis of cellular automata make essential use of their simple deterministic structure. One must find out to what extent results for the overall behaviour of cellular automata are changed when imperfections are introduced into them. The imperfections can be of several kinds. First, the cellular automaton rules can have a probabilistic element (e.g., [17, 34, 35]). Then for example each site may be updated at each time step according to one rule with probability , and according to another rule with probability . A second class of imperfections modifies the homogeneous cellular automaton lattice. One may for example take different sites to follow different rules. Or one may take the connections that specify the rules on the lattice to be different at different sites. In an ordinary cellular automaton, the values of all the sites are updated simultaneously, using the previous values of the sites in their neighbourhoods. One may consider the effect of deviations from this synchronization, allowing different sites to be updated at different times [36]. Finally, each site is usually taken to have a discrete set of possible values. One could instead allow the sites to have a continuum of values, but take the rules to be continuous functions with sharp thresholds.

Several classes of models can be considered as imperfect cellular automata. Directed percolation is directly analogous to certain cellular automata in the presence of noise [35]. The patterns generated with time by noisy cellular automata also correspond to the equilibrium configurations of spin systems at finite temperature [35]. And if inhomogeneities are introduced into the cellular automata, they give spin glass configurations. When nonlocal connections and asynchronous updates are introduced, models analogous to Boolean or neural networks are obtained (e.g., [37]).

Even an arbitrarily small imperfection in a cellular automaton can have a large effect at arbitrarily large times. However, small imperfections very often do not affect the overall behaviour of a cellular automaton. There is often a critical magnitude of imperfection at which essentially a phase transition occurs, and the behaviour of the cellular automaton changes suddenly. One can presumably find such transitions as a function of noise and other imperfections in many different cellular automata (cf. [34, 35]). Often the transitions should be associated with critical exponents; one expects that several universality classes may be identified. Note that even one-dimensional cellular automata can exhibit phase transitions at nonzero values of imperfection parameters if imperfections are introduced in such a way that for example certain initial states still evolve as they would without the imperfections.

Given a pattern generated by a cellular automaton with imperfections, as might be obtained in a physical experiment, one may consider how the basic cellular automaton rule could be deduced. One could lay down a definite grid, and then accumulate histograms of the new site values obtained with all neighbourhoods, and thereby deduce the cellular automaton rule (it will not necessarily be unique, since certain neighbourhoods may never appear) [13]. This procedure accounts for imperfections due to noise, but not for imperfections such as deformations of the lattice. It appears that an iterative optimization approach must be used to treat such imperfections.

previous  l  next