 |
 |
Pawel
Siwak Cellular automata |
Pawel Siwak
Cellular automata
Cellular automata
General and
classical cellular automata
Some events from the history
General and classical cellular automata
We view the cellular automata (CAs) as a computational model. They have the form of (regular) nets of identical interacting automata, called the cells. The CA model is strictly parallel: all cells change their states simultaneously. In the one dimensional (1-d) case a net may be such that each cell has r left and r right neighbours, as it is shown in Fig. 1 for r = 1.
Let us start with a model called here the general cellular automaton. This model distinguishes states of cells from their output symbols. Such a cellular net is defined as CN = (C, n , h ), where:
C = {ci} is a set of cells which are Moore automata c = (S, S , W , d , l , s0); i Î Z,
n : C ® 2C is a neighbourhood function; e.g. n (ci) = {ci-r, ..., ci-1, ci+1, ..., ci+r}. Usually the neighbours of a cell ci are specified by a set Ni = {i-r, ..., i-1, i+1, ..., i+r} of their indices,
h : W 2r ® S is a function that couples the cells.
Fig 1. Linear net (r = 1) of the general CA; the outputs w i of cells are distinguished from their states si.
At each instant t of time all cells in a net operate simultaneously (-¥ < i < ¥) according to:
Now, let us recall the nets called here classical CA. Such nets consist of Moore automata without outputs (l = id). In this case a single set A is assumed (A = S = W ), and called the set of sites (or states). The input alphabet of a cell is given by S = A2r, thus the functions l , h and d , that described the operation of general model, can be replaced by a single function A2r+1 ® A. This function is usually interpreted as identical with d : A2r+1 ® A and is called a local function of the model. Note, that such terms like rule, or LUT (look-up-table) are also in use for d . This model is very popular in literature (that is why it is called here classical). But sometimes, when the simulated phenomena require a distinction between states and output signals of cells, this model may be not sufficient.
In classical CAs, the global state of a net at some time t is described by a sequence at of the states of all cells in the net. This global state is also called the current configuration. The next configuration at +1 emerges as a result (-¥ < i < ¥) of updating simultaneously of all symbols from at :
The resulting global map at ® at +1 will be denoted by g (at ) = at +1.
For r = 1, the function d : A3 ® A can be considered as the set of all 4-tuples (a, b, c, d) Î A4, such that d (a, b, c) = d, where the results d are assumed to be placed on the position of b (one may say that b is updated). Any such 4-tuple will be called the elementary rule (ER) of the model. This convention allows us to distinguish five levels of cellular processing. These are:
the level of a single elementary rule,
the level of sets of ERs and families of such sets; this level supports the particles of CA,
the level of the local function d ,
the level of the global mapping g (when entire configuration changes; at ® at +1, and
the level of the computational task; a conversion of given at to a final at +k by iterating of g.
In the case of a finite CA, usually periodic boundary conditions are assumed. Also it is assumed that an initial state s0, denoted here by 0, and called the quiescent state, is such that d (0, 0, 0) = 0. In the binary case, when A = {0, 1}, the local function d : A2r+1 ® A is a Boolean function.
Fig. 2. Classical CA interpreted as a multilayer net of gates d : A3 ® A.
The images of computations performed by CA are presented on space-time (ST) diagrams, in (i, t ) coordinates. Successive configurations at , at +1, at +2, ... are placed in the consecutive rows. Note also, that the ST diagram of CA model can be interpreted as a multilayer net of gates d , as shown in Fig. 2.
Example 1. Consider a 2-d general cellular automaton CN1 = (C, n , h ) given in Fig. 3. It is assumed that input and output alphabets of cells are unified S = W = A = {0, 1} and the set of states is S = {0, 1, 2, 3, 4, 5, 6}. Let us choose the coupling function h : W 4 ® S to be XOR operation:
si, j = w i-1, j Å w i, j+1 Å w i+1, j Å w i, j-1.
Fig. 3. 2-d cellular net CN1 = (C, n , h ); seven state cells and von Neumann’s neghbourhood.
To start a computation in general net it is necessary to choose an initial configuration, or to be more specific, an initial pattern of states. Some initial pattern of states (with three automata in nonzero states) is shown in Fig. 4 together with its evolution during three consecutive steps of time t . Note that one can observe three entirely different aspects of the computation of a net: the states, the outputs or the inputs of cells.
Fig. 4. Sequence of patterns: states, outputs and inputs of evolving 2-d cellular automaton CN1 (zeros are shown as empty squares).
A pixel view on the same cellular automaton is shown in Fig. 5.
Fig. 5. Three pixel snapshots of evolving net CN1 show states, outputs and inputs of the cells.
Example 2. Now, we are going to illustrate the classical model of 1-d CA showing a task of binary to unary (B/U) code conversion. This task assumes that initial configuration a0 contains an integer L ³ 0 in its binary form. The string a0 should be transformed by a cellular automaton to some final stable (under g ) configuration which represents the same integer in its unary form. This task was posed and partially resolved in [GMM]. Here we recall a 5-state complete solution from [Si-SSG]. The time of conversion in this solution is T = 2L + 3.
Table 1 [Si-SSG], [Si-IFC]. 74 elementary rules of cellular B/U code conversion.
Our 1-d cellular automaton capable of B/U code conversion is given by: A = {0, 1, +, ´ , × }, radius r = 1 and the local function d : A3 ® A shown in Table 1. The rows of each table determine the state of the cell’s left neighbour, the columns determine the state of the cell’s right neighbour, and the head of each table shown in a box corresponds to current state of a cell. Note that not all ERs are specified; only 74 suffice to support B/U code conversion. A dot ² × ² denotes the quiescent state, thus the ER of the form (× , × , × , × ) is also included to the set.
One may check how this cellular conversion proceeds using the ST diagram shown below. Initial configuration a0 contains the numbers L from 0 to 7. The resulting unary code of L is seen as a segment of L consecutive elements x.
To understand how the conversion is organized note that the binary segment of the initial configuration operates like a residue number system (RNS) counter; it is decremented. On the right hand side of the counter two waves are generated. At the beginning of counting the front wave starts; its speed is 1/2. At the end of counting the final wave arises; it has the speed 1/1. When the waves meet, the final configuration is stabilised. The process can be observed also on pixel ST diagrams shown in Fig. 6 for a wider range of values of L.
Fig. 6. ST diagram of B/U code conversion for: 0 £ L £ 28, 29 £ L £ 42 and 43 £ L £ 52.
The ST diagrams can reveal certain characteristic coherent objects which are classified as particles. E.g. the string ...xx1xx... exhibits periodic evolution for the set R = {(x, x, x, x), (x, x, 1, x), (x, 1, x, x), (1, x, x, 1)} of ERs. This pair, that is the string and set R of ERs, represents the final chasing wave mentioned above. In this sense the level of subsets of ERs supports the particles.
Some events from the history: cellular automata as a computational model
1952 J. Von Neumann, inspired by S. Ulam, describes a 2-D cellular net capable of reproducing itself (5neighbours29states)-type net 1961 F. Hennie: studies of iterative arrays 1962 E. F. Moore’s Garden-of-Eden (GOE) theorem (and later Myhill’s converse theorem) In a series of papers (and in the book [HS]), J. Hartmanis and R. E. Stearns describe a relation between the global and local behaviour of automata nets (state assignment problem) 1965 P. Fisher shows a CA which may generate prime numbers A. J. Atrubin uses a linear CA to perform multiplication of binary numbers 1966 A. Waksman (in 1967 R. Balzer) shows a solution to the firing squad synchronization (FSS) problem 1967 M. Minsky finds a “simple” universal Turing machine with 7 states and 4 tape symbols R. C. Minnick discusses (survey in Journal of the ACM) cellular arrays form the point of view of the switching circuits 1968 E. F. Codd improves the von Neumann’s model: (5n8s) space is computation-construction universal 1969 H. Yamada, S. Amoroso. The beginning of a study of tesselation automata 1970 J. H. Conway introduces his famous game of life 2-D model (9n2s) 1971 A. R. Smith shows a 1-D universal (3n18s) CA 1972 G. Herman solves the French flag problem, and a synchronisation of growing filaments in CA 1973 S. A. Kauffman starts his research on random Boolean networks - a model of genes’ expression T. Yaku analyses the constructibility of a configuration in some CA 1974 GOE of Conway’s Life is found by R. W. Gosper group (MIT), and J. Hardouin-Duparc (France) F. Nourai and R. S. Kashef construct a 2-D cellular universal computer (5n4s) 1976 R. Smith gives a survey of polyautomata theory H. Takahashi describes the relations between cellular automata, iterative nets of FSMs and their limit sets Analysis of the completness problems starts (M. Nasu, N. Honda, then A. Maruoka, M. Kimura) 1978 W. I. Grosky analyses the existence of GOE configurations; U. Golze investigates the simulating possibilities of some cell spaces 1979 Studies of the properties of global mappings induced by cellular automata begin (S. Noguchi, M. Harao) Only some maps are decomposable in general tessallation structures (J. T. Butler) 1981 C. R. Dyer, A. Rosenfeld. Introduction of triangle cellular automata 1982 H. Umeo characterises relations between one-way CA and Turing machines 1984 S. Wolfram popularises the 1-D binary cellular automata O. H. Ibarra starts the studies of linear structures (cellular, iterative, systolic, trellis) 1986 J. K. Park, K. Steiglitz and W. P. Thurston discover soliton-like coherent entities in a one-way CA (a model called parity rule filter cellular automaton) 1987 J. Mazoyer starts the studies on signals in CA; e.g. gives an optimal six state solution to FSS problem, showes a 1-D universal CA with 1-bit communication (3n56s) restriction, etc. T. Serizawa describes the simplest known 2-D universal CA model (5n3s) J. Albert and K. Culik II describe a 1-D totalistic universal CA (3n14s) 1990 K. Lindgren and M. Nordal convert Minsky universal TM to a 1-D universal CA (3n7s)
Last modiefied: 07/09/09
