MUTATIONS OF THE "GAME OF LIFE": A GENERALIZED CELLULAR AUTOMATA PERSPECTIVE OF COMPLEX ADAPTIVE SYSTEMS
Authors: DOGARU RADU , CHUA LEON O. 
Published: April 2003

This paper presents a novel approach for studying the relationship between the properties of isolated cells and the emergent behavior that occurs in cellular systems formed by coupling such cells. The novelty of our approach consists of a method for precisely partitioning the cell parameter space into subdomains via the failure boundaries of the piecewise-linear CNN (cellular neural network) cells [Dogaru & Chua, 1999a] of a generalized cellular automata [Chua, 1998]. Instead of exploring the rule space via statistically defined parameters (such as λ in [Langton, 1990]), or by conducting an exhaustive search over the entire set of all possible local Boolean functions, our approach consists of exploring a deterministically structured parameter space built around parameter points corresponding to "interesting" local Boolean logic functions.

The well-known "Game of Life" [Berlekamp et al., 1982] cellular automata is reconsidered here to exemplify our approach and its advantages. Starting from a piecewise-linear representation of the classic Conway logic function called the "Game of Life", and by introducing two new cell parameters that are allowed to vary continuously over a specified domain, we are able to draw a "map-like" picture consisting of planar regions which cover the cell parameter space. A total of 148 subdomains and their failure boundaries are precisely identified and represented by colored paving stones in this mosaic picture (see Fig. 1), where each stone corresponds to a specific local Boolean function in cellular automata parlance. Except for the central "paving stone" representing the "Game of Life" Boolean function, all others are mutations uncovered by exploring the entire set of 148 subdomains and determining their dynamic behaviors. Some of these mutations lead to interesting, "artificial life"-like behavior where colonies of identical miniaturized patterns emerge and evolve from random initial conditions. To classify these emergent behaviors, we have introduced a nonhomogeneity measure, called cellular disorder measure, which was inspired by the local activity theory from [Chua, 1998]. Based on its temporal evolution, we are able to partition the cell parameter space into a class U "unstable-like" region, a class E "edge of chaos"-like region, and a class P "passive-like" region. The similarity with the "unstable", "edge of chaos" and "passive" domains defined precisely and applied to various reaction–diffusion CNN systems [Dogaru & Chua, 1998b, 1998c] opens interesting perspectives for extending the theory of local activity [Chua, 1998] to discrete-time cellular systems with nonlinear couplings. To demonstrate the potential of emergent computation in generalized cellular automata with cells designed from mutations of the "Game of Life", we present a nontrivial application of pattern detection and reconstruction from very noisy environments. In particular, our example demonstrates that patterns can be identified and reconstructed with very good accuracy even from images where the noise level is ten times stronger than the uncorrupted image.