Formalisations of Cellular Automata
The theories of complexity are the understanding of how independent agents are interacting in a system to influence each other and the whole system [32]. Surprising computational tasks could result from interactions of independent agents in complex systems as the emergence of computation is a hot topic in the science of complexity [34]. A promising environment to study emergent computation in cellular automata [31] which are the simplest mathematical representation of complex systems [8]. They are uniform frameworks in which the simple agents are cells evolving through time-based on a local function, called the transition rules [33]. Emerging computation in cellular automata has different forms. Some have studied specific computations like density and synchronization tasks [7, 14, 15, 18, 28] and pattern recognition [35]. While others have considered Turing-universal automata [1, 2, 10, 12, 16, 19], i.e. Automata encompassing the whole computational power of the class of Turing machines [17]. The well-established problems of universality in cellular automata remain an area where amazing phenomena at the edge of theoretical computer science and non-linear science can be discovered. One of the demonstrations of universality is based on mobile self-localized patterns of non-resting states [19], called gliders and their generators called glider guns which, when evolving alone, periodically recover their original shape after emitting several gliders. As an example, the famous Game of Life of Conway et al. [4] has been shown universal thanks to a gun called Gosper gun. This demonstration uses gliders to carry information and glider guns as a clock. We aim to construct an automatic system for the discovery of Turing-universal cellular automata. The first step presented here is the discovery of gliders and glider guns. The search for gliders was notably explored by Adamatzky et al. With a phenomenological search [13], Wuensche who used his Z-parameter and entropy [36], and Eppstein [6]. Lohn et al. [11] and Ventrella [30] have searched for gliders using stochastic algorithms.
Number of Automata
The number of automata in E is the number of possible transition rules δ: S8+1 → S. There are 29 = 512 different rectangular 9-cell neighborhood states (including the central cell) so space E contains 2512 automata. An automaton of E can be described by telling what will be the new state of a cell at the next generation depending on its neighborhood as shown in Fig. 9.2. The number of automata of I depends on how many subsets of isotropic neighborhood states the 512 different rectangular 9-cell neighborhood states can be put.
Definitions of Patterns
A pattern P is a configuration of cells in a 2D space with relative positioning to one another. The evolution of P in the automaton A is the sequence (P A t )t≥0 such that P A 0 is the pattern P positioned alone in a 2-dimensional lattice Z2. A pattern is included in a configuration cat of an automaton A of the space E if the cat is the pattern P is positioned possibly with other cells. A pattern is included in the cat of an automaton A of the space I if a cat is P after applying rotations and symmetries possibly with other cells around. Figure 9.9 shows the R-pentomino of Game of Life after applying rotations and symmetries and Fig. 9.10 shows this pattern included in a configuration.
Last word
To determine the set of automata B that accepts a pattern P of an automaton A, an image-filtering of P A t for all t is used. For all t, all neighborhoods in P A t, called used neighborhoods, are memorized. For the neighborhoods that have been memorized, δb is determined by δa, and only for the other ones, the function δb is free. Let n be the number of neighborhoods that have been memorized. For 512 − n neighborhoods, δb is free so 2512−n automata accept the pattern P . This process is shown in Fig. 9.17 for the glider of the Game of Life at generations 0 and 1. 29 neighborhoods have been memorized leading to having 2483 automata of the space E that accept this glider during the two first generations in this direction.
