Francoise J.-P., Naber G.L., Tsun T.S. (editors) Encyclopedia of Mathematical Physics

Подождите немного. Документ загружается.

Cellular Automata

M Bruschi, Universita

di Roma ‘‘La Sapienza’’, Rome,

Italy

F Musso, Universita

‘‘Roma Tre’’, Rome, Italy

What is a Cellular Automaton?

Cellular automata (CAs) were first introduced by

J von Neumann in his investigation of ‘‘complexity,’’

following an inspired suggestion by S Ulam. But in the

last 50 years they have been investigated and used in a

number of fields; widely diff erent terminologies have

been used by researchers that now it is difficult even

to give a precise general definition of a CA. Thus,

some definitions and approximations are in order.

First a broad definition:

1. have a number of cells (boxes);

2. at any (discrete) time step, any cell can present

itself in a certain ‘‘state’’ among a finite number

of different states;

3. the state of any cell can change (evolve) from a

time step to the subsequent time step; a nd

4. there is a rule (evolution law, EL) which

determines this transition.

Note that the number of cells can be finite or infinite;

thecellscanbearrangedonaline,onasurface,inthe

ordinary three-dimensional (3D) space, or possibly in a

hyperspace (in any case, the cells can be numbered); the

different states of a cell can be denoted by integer

numbers but, in different contexts of application of

CAs, different imaginative pictures have also been used

(e.g., different colors, dead and living cells, number of

balls in a box, etc.); the evolution of a CA proceeds in

finite time steps (time is also discrete); the EL, provided

that it is effective on any possible configuration of a

given CA (computability), is otherwise completely

arbitrary (indeed, there are not only deterministic and

probabilistic ELs, but also those that ‘‘evolve’’ in time –

following a meta-EL, which in turn can be determinis-

tic or probabilistic).

Consider some examples of CAs.

Example 1 (CA1) Consider a linear array of seven

boxes (cells; one can number them c(i), i = 1, 2, ..., 7).

Each box can be empty or it can contain a ball (so

there are just two states for each cell). Given a

configuration of this CA at time t, what happens at

time t þ 1(EL)?

(i) the state of the first box c(1) never changes;

(ii) for each other box c(i), i = 2, 3, ...,7;

(iia) if the box is empty and the box on its left is

empty then put a ball in the box;

(iib) if there is a ball in the box and also there is a ball

in the box on its left then empty the box.

An example of the evolution of such a rather trivial

CA is given in Figure 1.

A more precise notation can now be established.

First, let us denote the state of a cell at time t by a

‘‘state function,’’ say S. According to the point (iib)

above, the number of possible states is arbitrary but

finite: denote this number by the positive integer M

(M > 1). Then S takes values on a finite field, say

= Z=MZ = {0, 1, 2, ..., M  1} (in plain words,

we have denoted the M states for the CA by the

first M non-negative integers). Different cells can be

labeled with a progressive number: c(n), n = n

, n

1, ..., n

 1, n

; possibly, in case of an infinite

number of cells, one has n

!  1 and/or

! þ 1 . In the case of n

= 1, n

= 1, one

speaks of a unidimensional CA. Of course, the field S

depends on n as well as on time (remember that, for a

CA, ‘‘time’’ is a discrete variable: t = 0, 1, 2, ...). The

field S(n, t) describes completely the CA. If the EL is

deterministic, then one can determine (com-

pute) S(n, t) step by step for t > 0 from the initial

configuration S(n, 0) (initial datum, ID). Consider

only static ELs, namely those that do not change in

time. A further distinction can be made: there are

ELs such that the future state of the generic cell,

S(n, t þ 1), depends on the whole current configura-

tion of the CA (these are called nonlocal ELs) and

there are ELs for which S(n, t þ 1) depends only on

c (1) c (2) c (3) c

(4) c (5) c (6) c (7)

= 0

= 1

= 2

t = 3

= 4

= 5

= 6

= 7

Figure 1 A seven time-step evolution of CA1 starting from a

given ID (t = 0). Note that a stable configuration has been

reached at t = 6.

Cellular Automata 455

the current state of a finite number, say N, of cells

(local ELs):

fSðn þ k

; tÞg; i ¼ 1; 2; ...; N; k

2 Z

¼) Sðn; t þ 1Þ½1

Note that, in principle, the set of cells that

determine, according to the EL, the future state of the

generic cell n, could depend on n, namely one can have

N = N(n), as well k

= k

(n), i = 1, 2, ..., N(n)(see

CA2 below). In any case, such a set of cells is called

the interaction set (IS). Moreover, the distance from

the cell n of the farthest cell in the IS is called

the range R (of the interaction): R = max( k

). If

IS  {c(n  R), c(n  R þ 1), ...c(n), ...c(n þ R  1),

c(n þ R)}, then this IS is called a neighborhood of

range R. It is, moreover, clear that, for unidimensional

CA, there exists at least one infinite subset of cells that

have the same state. If there is only one such subset,

then it is called the vacuum set and the state of its

cells is called vacuum state: let V denote the value of

this state (0  V < M, S(n, t) !

n!1

V).

Example 2 (CA2) An example of CA with

n-dependent IS (M = 2, R = 3, V = 0). This is the

EL: the cell c(n) changes its state (0 ! 1, 1 ! 0) iff

(i) n is even and at least one of the two cells on its

left is not in the vacuum state;

(ii) n is odd and one or three of the three cells on its

right are not in the vacuum state.

An example of the evolution of such a CA is given

in Figure 2.

Usually, only a subclass of ELs is considered for

which the phenomenon of vacuum excitation

cannot occur. Namely, during the evolution of

the CA, an infinite subset of the vacuum set

cannot change its state in just one time step. In

other words: if the set of cells starting from the

first c ell and ending with the last one for which

S(n, t) 6¼ V be called population set (PS), then PS is

a finite set at each time.

Of course, one can easily devise an EL for which

this is not true; nevertheless, the EL itself is still

valid (computable), for instance,

Example 3 (CA3) This is an unidimensional CA,

namely there are infinite cells on a line (n 2 Z). The

cells have M states and V = 0; the EL reads:

the state of each cell cycles in the set of available states

ð0 ! 1; 1 ! 2; ...; M  2 ! M  1; M 1 ! 0Þ

Note that the range R is zero, there is a vacuum

excitation; nevertheless, the EL is effective.

Deterministic, static, and local ELs that do not give

rise to vacuum excitation are called normal ELs (NELs).

Since M, N are finite for an NEL, one can give the

NEL itself as a table, considering every possible

configuration of the IS and specifying the outcome

for each configuration (note that there are M

possible configurations) .

Example 4 (CA4) n 2 Z, M = 2, V = 0, IS  {c(n),

c(n  1), c(n þ 2)}, N = 3, R = 2. The EL is:

Sðn; tÞ 00001111

Sðn  1; tÞ 00110011

Sðn þ 2; tÞ 01010101

Sðn; t þ 1Þ 01101101

½2

An example of the evolution of such a CA is given

in Figure 3.

However, these NELs can also be given in an

alternative repre sentation (more useful in view of the

extensions of the concept of CA itself, see below).

Namely, an NEL can be given as a discrete-time

EL for the state function S (n, t) in the finite field

= {0, 1, 2, ..., M  1}.

Figure 2 Three hundred and eighty time steps of CA2, starting

from a random chosen initial configuration. Note the left–right

asymmetry due to the asymmetry of its IS and EL.

Figure 3 Four hundred and sixty-one time steps of CA4,

starting from a random chosen PS of 50 cells.

456 Cellular Automata

For example, the NEL above for CA4 can be

expressed as follows:

Sðn; t þ 1Þ¼

Sðn  1; tÞþSðn; tÞþSðn þ 2; tÞ

þ Sðn; tÞSðn þ 2; tÞ

þ Sðn  1; tÞSðn; tÞSðn þ 2; tÞ½3

Here and in the following, the symbol ¼

denotes a

congruence mod M.

Another example is the following.

Example 5 (CA5) n 2 Z, M = 3, N = 3, V = 0, R = 1,

IS  {c(n  1), c(n), c(n þ 1)}. The NEL is:

Sðn; t þ 1Þ¼

Sðn  1; tÞþSðn; tÞþSðn þ 1; tÞ

þ 2Sðn  1; tÞSðn þ 1; tÞ½4

An example of the evolution of such a CA is given

in Figure 4.

Classification of ELs

Considering a CA with given M > 1, N  1, the

number L of possible deterministic, static ELs is

LðM; NÞ¼M

ðÞ

½5

Of course, this number can be very large for

relatively small values of M and N also. Never-

theless, it is a finite positive integer, so that, for

given M, N, one could denote every EL by an

integer number and investigate the typical behavior

of each EL. A considerabl e reduction of this

number is obtained if one limits attention to

totalistic ELs, namely to those whose outcome

depends only on the global configuration of the

IS, often just on

ðn;tÞ¼

i¼1

Sðn þk

Þ; i ¼1;2;...;N; k

2Z ½6

Deep and extensive computer investigations have

been exploited for unidimensional CAs with small

values of M, N. Surprisingly enough, it seems that

the typical behavior of all these CAs can be (roughly

and heuristically) classified in just four classes

(Wolfram 2002):



Class 1 (simple): possibly after a complicated

transient, simple patterns emerge.



Class 2 (fractalic): possibly after a transient,

overall regular nested structures are obtained.



Class 3 (chaotic): complicated but seemingly

random behavior.



Class 4 (complex): possibly after a transient,

localized structures emerge that interact in com-

plex ways.

Due to the looseness of the above definitions,

perhaps a better way to distinguish between classes

is to train one’s eye. Consider some examples of

CAs for each class: the typical behavior of class-1

CA is shown in Figures 5 and 6, of class-2 CA in

Figures 7 and 8, of class-3 CA in Figures 4 and 9,

of class-4 CA in Figures 10 and 11. Note, however,

that often one has ‘‘mixed type’’ CA: for example,

CA4 is of class 1 on the right and of class 2 on

the left (see Figure 3); Figure 12 exhibits a CA

where the typical behaviors of classes 2 and 3 are

superimposed.

Extensions

The concept of a CA is so simple that many

extensions of the above-sketched definition of a

CA can be easily devised. A (nonexhaustive) survey

of such extensions follows.

Figure 4 Four hundred and sixty-one time steps of CA5,

starting from a random chosen PS of 50 cells.

Figure 5 A class-1 CA: every ID rapidly evolves to

periodic structures; M = 3,V = 0, R = 2, EL: S(n, t þ 1) =

S(n, t)þ

S(n 1, t)S(n þ 2, t).

Cellular Automata 457

Vector CA

In this extension, the state function S(n, t)is

considered as a ‘‘vector,’’ namely S(n, t) 

(n, t), S

(n, t), ...S

(n, t)), L being a positive inte-

ger. Each component S

(n, t)(l = 1, 2, ..., L) takes

values in a finite field, say Z

= {0, 1, 2, ..., M



1}, and evolves, according to some EL, interacting

with the other components. Of course, one can give

separately the time evolution for each component;

however, it is also possible to give a global

representation of a vector CA, introducing a global

function

S(n, t) that takes values in the finite field

, M = M

...M

; for example,

Sðn; tÞ¼S

ðn; tÞþ

L1

l¼1

ðn; tÞ

k>l

½7

Thus, in a sense, vector CAs are still usual CAs

with a complicated EL.

Example 6 (CA6) A two-com ponent vector CA:

ðn; t þ1Þ¼

ðn; tÞS

ðn þ1; tÞ

þðM

1ÞS

ðn 1; tÞS

ðn;t Þþc

½8

ðn; t þ 1Þ¼

ðn  1; tÞS

ðn; tÞ

þ S

ðn; tÞS

ðn þ 1; tÞþc

½9

Figure 8 A class-2 CA: a double fractal structure appears; M = 4,

V = 0, R = 2, EL: S(n, t þ1) =

S(n 2, t) þS(n, t) þS(n þ2, t):

Figure 7 A class-2 CA: Sierpinsky triangles appear; M = 2,

V = 0, R = 1, EL: S(n, t þ 1) =

S(n 1, t) þ S(n þ 1, t).

Figure 6 A class-1 CA, a random ID vanishes after 337

time steps, M = 5, V = 0, R = 2, EL: S(n, t þ 1) =

S(n 1, t)

S(n 2,t)þS(n þ1,t)S(n þ2,t)þS(n 1,t)S(n þ1,t) þS(n 2,t)

S(n þ2,t).

Figure 9 A class-3 CA: M = 5, V = 0, R = 2, EL: S(n, t þ 1) =

2S(n  1, t) þ S(n þ 1, t) þ S(n, t)(S(n þ 1, t) þ S(n þ 2, t)) þ

S(n  1, t)S(n þ 1, t).

458 Cellular Automata

The global behavior of this CA can be expressed,

for example, through the global state function

Sðn; tÞ¼M

ðn; tÞþS

ðn; tÞ½10

Obviously,

S 2 Z

with M = M

. Figure 13

represents the global behavior of this CA with

= 2, M

= 3, c

= 1, c

= 1, V = 0.

Note that this CA can be considered as an

extension of the celebrated qua dratic map.

Multidimensional CA

Up to now we have considered CAs with finite number

of cells (finite CAs) or with an infinite number of cells

arranged on a line (unidimensional CAs). Now we

consider CAs with cells arranged on a surface,

usually a plane (bidimensional CAs), or on 3-space

(tridimensional CAs), or even on a hyperspace (multi-

dimensional CAs). In any case, if the number of cells

is finite, the evolution of such CAs, according to an

NEL, must end up to a final cycle: this is due to the

finiteness of the ‘‘phase space’’ (thus, these CAs should

be classified as class 1; however, note that, if the

‘‘phase space’’ is large enough, the dynamics of

Figure 10 A class-4 CA (Wolfram CA 110): M = 2, V = 0, R = 1,

EL: S(n,t þ1)=

S(n,t) þS(n þ1,t) þS(n,t)S( n þ1,t) þS(n 1,t)

S(n,t)S(n þ1,t).

Figure 11 A class-4 CA. Note the interacting moving struc-

tures on the left and on the right; note also the apparently

chaotic behavior in the center; M = 2,V = 0,R = 2,EL: S(n,t þ 1)=

S(n,t) þ S(n þ 1,t) þ S(n  1,t)S(n þ 2,t).

Figure 12 A mixed-class CA: a fractalic structure is super-

imposed on a chaotic one; M = 4, V = 0, R = 2, EL: S(n, t þ 1) =

S(n, t)(S(n  2, t) þ S(n þ 2, t)) þ S(n  1, t)S(n þ 1, t).

Figure 13 Global behavior of the vector CA6.

Cellular Automata 459

such CAs can still be very rich). Usually, one

considers an infinite number of cells tessellating

the whole s-space, s = 2, 3, ... (e.g., squares o r

hexagons on the plane, cubic cells in 3-space). The

changes in the previous notation and definitions are

plain: for exam ple, for a bidimensional CA, the state

function depend s now on two discrete ‘‘space’’

variables (S(n

, n

, t), n

2 Z, n

2 Z); furthermore,

there is a greater freedom in choosing a neighbor-

hood of range R. Two most-u sed neighborhoods of

range 1 are shown below:

Neumann neighborhood





} 





Moore–Conway neighborhood





} 





½11

The most famous (and interesting) bidimensional

CA is ‘‘Life’’, introduced by J H Conway, which is

discussed next.

Example 7 (CA ‘‘Life’’; Moore–Conway neighbor-

hood, V = 0, M = 2). A cell in the vacuum state 0 is

called ‘‘dead’’; a cell in the state 1 is called ‘‘alive.’’

The EL is as follows:

(i) If a cell is dead at time t, it comes alive at time

t þ 1 if and only if exactly three of its eight

neighbors are alive at time t (reproduction).

(ii) If a cell is alive at time t, it dies at time t þ 1ifand

only if fewer than two (loneliness) or more than

three (overcrowding) neighbors are alive at time t.

Clearly, this is a totalistic NEL. Now considering

the explicit form of  (see [6]):

ðn

; n

;tÞ¼Sðn

; n

;tÞ

¼1

Sðn

þk

; n

þk

; tÞ½12

the above EL can be simply expressed as:

Sðn

; n

; t þ 1Þ¼

3;

þ 

2;

Sðn

; n

; tÞ½13

where 

3, 

is the Kroenecker symbol.

Life is a class-4 CA; it exhibits a rich variety of

interesting structures: stable structures, oscillators

(periodic structures), gliders and ships (moving

structures), emitters and absorbers (namely, struc-

tures that, after a time period, reconstitute them-

selves, but meanwhile they have emitted or adsorbed

moving structures). These structures are essential to

prove that Life can be used to construct a universal

Turing machine (see below). One can get a rough

idea of such ‘‘richness’’ from Figure 14.

As in the previou s case of vector CA, one could

object that also multidimensional CAs are not true

extensions of the unidimensional CAs. Indeed, since

the whole set of cells is still a countable set, one

could number the cells with just a discrete ‘‘space’’

variable (say n 2 Z ). For example, in the case of a

square tessellation of the plane, we could enumerate

the cells in the plane starting from the origin as

follows:

22 !

21 20 19 18

13 12 11 4 5 6 17

14 9 10 3 2 7 16

15 8 101815

16 7 2 310 914

17 6 5 4111213

18 19 20 21

22

½14

Thus, any multidimensional CA could in principle

be viewed as a unidimensional one. Of course, one

has to pa y a price for this: ISs and ELs that are

simple for a multidimensional CA become cumber-

some for its unidimensional version and vice versa.

Higher Time Derivatives

Up to now, we have considered CAs whose evolved

state S(t þ 1) depends only on the state S (t), namely

the state of the CA itself at the previous time step. In

other words the EL involves just the first (discrete)

time derivative (1

CA). One can easily extend all the

previous definitions to consider higher-order disc rete

time derivatives (K

CA). Of course, the ID and the IS

for such a CA involve the state of the CA at K

subsequent time steps.

An example of a unidimensional 2

CA is given

below.

Example 8 (CA7) M = 3, V = 0, R = 1. The EL is:

Sðn; t þ1Þ¼

Sðn 1; tÞþSðn; t 1ÞþSðn þ1; tÞ½15

An example of the evolution of such a CA is given in

Figure 15.

460 Cellular Automata

It is plain that taki ng a suitable continuum limit

of a K

CA one gets a partial differential equation of

order K for the evolution. However, there are also

special and interesting CAs, called ‘‘filter’’ CAs,

that in a suitable continuum limit end up in integral

evolution equations. For a filter unidimensional

CA, the evolved state at the cell n, S(n, t þ 1),

depends also on the (already) evolved states of the

cells on its left (or right): for example, an NEL of

the type

Sðn; t þ 1Þ¼

FðSðn þ k

; tÞ; Sðn 

; t þ 1ÞÞ

i ¼ 1; 2; ...; N; k

2 Z

j ¼ 1; 2; ...;

2 N ½16

is still valid (computable). Extensions to K

CAs or

vector CAs or multidimensional CA are plain. Very

often filter CAs exhibi t a class-4 behavior with

particle-like structures moving and interacting in a

complex way; see the following example and

examples in the next section.

Example 9 (CA8) M = 2, V = 0, R = 2. The EL is:

Sðn; t þ 1Þ¼

Sðn  1; t  1ÞSðn  2; tÞ

þ Sðn; tÞþSðn þ 1; tÞSðn þ 2; tÞ½17

An example of the evolution of such a CA is given

in Figure 16.

Invertible CA

For most of the ELs there is a loss of information

in the course of the evolution (see, e.g., Figures 5

and 6). Indeed, different definitions of ‘‘CA

entropy’’ have been introduced to measure the

‘‘randomness’’ in the behavior of a given CA.

However, since CAs are im portant in physical

(e) (f)

(a) (b)

Figure 14 CA ‘‘Life’’: (a) Time 0. Near the lower border, five

stable structures (from the left to the right: a ‘‘block’’, a ‘‘boat’’, a

‘‘ship’’, a ‘‘loaf’’, a ‘‘beehive’’); near the left border three ‘‘blinkers’’

(period-2 oscillators); near the right corner, a symmetric structure

that, in one time step, evolves into a ‘‘pulsar’’ (a period-3

oscillator), on the left-up corner a ‘‘glider’’ (a moving structure);

on the right-up corner a ‘‘medium weight spaceship’’ (another

moving structure); in the center, a configuration that vanishes in a

few time steps. (b) Time 1. The structures on the lower border are

unchanged, the blinkers, the glider, and the space ship are in an

intermediate state, on the right border, the pulsar starts to pulse.

original configurations (periodic structure with period 2), the

pulsar, the glider and the spaceship are in another intermediate

state. (d) Time 3. The pulsar is in its second state, the glider and

the spaceship in their third, the structure in the center is going to

vanish. (e) Time 4. The pulsar has completed its pulsation (period-

3 oscillator, see Figure 14b); the structure in the center has

vanished, the glider and the spaceship have recovered their

original configurations (see Figure 14a) but meanwhile they have

moved of a cell in four time steps (1n4 of the highest velocity

attainable by a moving structure in a CA of range 1). The glider is

moving downward and to the right, the space ship in horizontal to

the left. (f) Time 60. The space ship has almost completed its

crossing, the glider has reached the center and it is in a collision

route with the pulsar.

Figure 15 CA7, clearly a class-2 CA.

Cellular Automata 461

modeling as well as in cryptography and data

compression, there is great interest in a special

subclass of CAs which are ‘‘invertible’’ (time

reversible). Namely, for an ‘‘invertible’’ CA fol-

lowing a given EL a nd starting from an arbitrary

ID, there exists an ‘‘inverse’’ EL such that one

can recover the ID from the evo lved states.

Invertible CAs can be easily devised in the case of

CA (K > 1). For example, if K = 2, 3 ..., one can

consider ELs of the form

Sðn;t þ1Þ¼

Sðn;t K þ1ÞþFSðn þk

;t jÞ



½18a

where

i ¼ 1; 2; ...; N

; k

2 Z

j ¼ 0; 1; 2; ...; K  2

½18b

and F is an arbitrary polynomial function.

It is then clear that the inverse EL reads

Sðn;

t þ1Þ¼

Sðn;

t K þ1Þ

þðM 1ÞF

Sðn þk

;

t þj K þ2



½19

Indeed, if an arbitrary ID evolves according to

the EL [18], then applying the inverse EL [19] to K

subsequent evolved states (taken in reversed order),

eventually the original ID is recovered (in reversed

order) (see the following exampl e).

Example 10 (CA9) A 6

CA: M = 2, V = 0, R = 1.

The EL is:

Sðn; t þ 1Þ¼

Sðn; t  5ÞþSðn; t  3ÞþSðn þ 1; t  2Þ

þ Sðn  1; t  1Þ

þ Sðn; t  2ÞSðn þ 1; t  2Þ

þ Sðn; tÞSðn  1; tÞ½20

The inverse EL, according to [19], reads

(Figure 17)

Sðn;

t þ 1Þ¼

Sðn;

t  5Þþ

Sðn;

t  1Þþ

Sðn þ 1;

t  2Þ

Sðn  1;

t  3Þ

Sðn;

t  2Þ

Sðn þ 1;

t  2Þ

Sðn;

t  4Þ

Sðn  1;

t  4Þ½21

Figure 16 CA8, a ‘‘filter’’ CA. Note the emerging of particle-like

structures moving to the left and to the right and interacting in

complex ways.

(a)

(b)

Figure 17 CA9, a 6 CA: (a) a 50 time-step evolution from a

peculiar ID; (b) a 50 time-step evolution of the inverse EL, starting

from the last six configurations of Figure 17a (taken in inverse

order); the ID of Figure 17a is recovered (in inverse order).

462 Cellular Automata

Of course, more complicated invertible ELs can be

devised. Invertible ELs can be also easily devised for

‘‘filter’’ CA, for example, if an NEL for a ‘‘filter’’ CA

reads

Sðn; t þ 1Þ¼

Sðn; tÞ

þ FðSðn þ k

; tÞ; Sðn 

; t þ 1ÞÞ ½22

where k

and

are positive integers

(i = 1, 2, ..., N; j = 1, 2, ...,

N) and F is an arbitrary

(polynomial) function, then it is invertible an d

the inverse NEL reads

Sðn;

t þ 1Þ¼

Sðn;

tÞþðM  1Þ

 Fð

Sðn þ k

;

t þ 1Þ;

Sðn 

;

tÞÞ ½23

Note that [22] is computable starting from

n = 1, whereas [23] is computable star ting from

n = þ1.

Example 11 (CA10) A 1.5

CA, M = 2, V = 0, R = 3.

The EL is:

Sðn; t þ 1Þ¼

Sðn; tÞþSðn  3; t þ 1ÞSðn  2; t þ 1Þ

þ Sðn þ 2; tÞSðn þ 3; tÞ

þ Sðn  2; t þ 1ÞSðn  1; t þ 1Þ

þ Sðn þ 1; tÞSðn þ 2; tÞ½24

Note that this EL is of the form [22]; therefore, it

is invertible (see Figure 18a). According to [23], the

inverse EL reads:

Sðn;

t þ 1

Þ¼

Sðn;

tÞþ

Sðn þ 3;

t þ 1Þ

Sðn þ 2;

t þ 1Þ

Sðn  2; tÞ

Sðn  3; tÞ

Sðn þ 2;

t þ 1Þ

Sðn þ 1;

t þ 1Þ

Sðn  1;

tÞ

Sðn  2;

tÞ½25

This CA exhibits a very rich dynamics: any

complex ID rapidly decays in a great variety of coherent

particle-like structures, steady or moving to the right or

(a)

(b)

Figure 18 CA10: (a) 230 time-step evolution, then the inverse EL is applied for 230 further time step in order to recover the initial

configuration. (b) Collisions between different kinds of particle-like coherent moving structures. The last collision (on the right) is

a solitonic one: the interaction produces just a phase shift, preserving number, shape, and velocities of the involved ‘‘particles.’’

(c) ‘‘Particles’’ moving with different velocities and interacting in complex ways (solitonic collisions, particle creations and annihilations).

(d) A particle goes through a nonhomogeneous medium and undergoes refraction by the medium itself.

Cellular Automata 463

to the left with different velocities. The interactions

between different particles may be solitonic (the

particles emerge unchanged but shifted) or annihila-

tion–creation phenomena can occur (see Figures 18a–d).

Applications of CAs

CAs as Universal Constructors and

Turing Machines

In the 1950s, von Neumann, who contributed to the

development of the first computer (ENIAC), decided

to work out a mathematical theory of automata.

Such a theory was finalized to give an answer to the

following question: is it possible to build an

automaton such that it allows universal computa-

tion (i.e., it embodies a universal Turing machine)

and, moreover, it is able to build (in order of

decreasing generality)

1. an arbitrary automata (universal constructor);

2. a copy of itself (self-reproducing); and

3. an automaton that is itself a universal Turing

machine (constructor)?

The last question von Neumann had intention to

address was if in the process of automata self-

reproduction (if possible) a process of evolution

could take place, that is, if a simpler automaton

could generate a more complex one.

In the beginning, the idea of von Neumann was to

describe, using mathematical axioms, an automaton

moving inside a warehouse and selecting various

elementary spare parts (e.g., ‘ ‘muscles,’’ switches, rigid

girders) and then assembling them into a new auto-

maton. While this original idea was very realistic, it was

also very difficult to pursue, so that von Neumann,

following a suggestion by Ulam, decided to consider his

questions in the more abstract framework of CAs.

The particular CA he considered is an infinite

square CA with 29 possible states. The transition rule

is dependent upon the cell to update and its north,

east, south, and west neighbor cell (the von Neumann

neighborhood). Among the 29 possible states there is

one state that is ‘‘quiescent’’ (the vacuum state).

von Neumann proved the existence of a configura-

tion of 50 000 cells immersed in a sea of quiescent

states that embodies a universal Turing machine and

that is a universal constructor. An infinite one-

dimensional ‘‘tape’’ is used to store a description of

the automaton to build. The universal constructor

reads the description on the tape, develops a

‘‘constructing arm’’ that builds the configuration

described on the tape in an unoccupied part of the

cellular space, makes a copy of the tape and finally

attaches it to the newly built automaton and retracts

the constructing arm. When on the tape, it stores a

description of the universal constructor itself, then it

self-reproduces. The total size of the self-reproducing

automaton amounts to 200 000 cells. (Some com-

puter simulations of von Neumann self-reproducing

automaton are available on the web.)

Since von Neumann’s CA is a very complex one,

it led researchers to think that a CA able to simulate

a universal Turing machine should also be quite

complex. The perspective changed completely after

the introduction of CA Life. Conway was looking

for a simple CA with a possible rich dynami cs;

however, it was subsequently realized that Life was

much more complicated that anyone could have

thought. Finally, thanks to the development of faster

computers that allowed visualization of the evolu-

tion of quite large populations and through the

contribution of a large number of researchers, it was

proved that a universal Turing machine could be

embedded in Life.

The discovery that even a simple CA such as Life

could incorporate a universal Turing machine led to

the question whether it could be possible to build a

universal Turing machine inside a simple one-

dimensional CA. This is indeed the case: up to

now, the simplest CA capable of universal computa-

tion is the W110 CA (see Figure 10), as proved

recently by Cook after a conje cture formulated by

Wolfram in 1985.

CAs for Computer Simulations

One of the major applications of CAs is the

computer simulation of various dynamical pro-

cesses. Even if CAs were not invented for this

purpose, they possess peculiarities that make them

particularly suitable for this task. The main advan-

tage of using a CA for a dynamical simulation is due

to their completely discrete nature that allows exact

simulations on a computer. Thus, any spurious

effect due to rounding errors is ruled out. Another

advantage is that the EL of a CA can be seen as a

function between finite sets. For this reason, one can

specify the EL through a ‘‘lookup table’’ (see [2]):

then when running the simulations, the computer

has only to access the table instead of computing the

function every time, shortening considerably the

computation time. Another great advantage of CAs

in computer simulations is that, for their very nature

(at least for local EL), they can be implemented on

parallel machines. These two concepts are at the

basis of dedicated computers for CAs simulations

developed by Toffoli, Margolus, and co-workers

(CAM series). The possibility to use efficiently

parallel computers for CA simulation could prove

464 Cellular Automata