Computer Application & Graphics
Computer Application & Graphics
Stephen Wolfram
The Institute for Advanced Study, Princeton, New Jersey 08540
Cellular automata are used as simple mathematical models to investigate self-organization in statistical
mechanics. A detailed analysis is given of "elementary" cellular automata consisting of a sequence of sites
with values 0 or 1 on a line, with each site evolving deterministically in discrete time steps according to
definite rules involving the values of its nearest neighbors. With simple initial configurations, the cellular
automata either tend to homogeneous states, or generate self-similar patterns with fractal dimensions
=1.59 or =1.69. With "random" initial configurations, the irreversible character of the cellular automa-
ton evolution leads to several self-organization phenomena. Statistical properties of the structures generat-
ed are found to lie in two universality classes, independent of the details of the initial state or the cellular
automaton rules. More complicated cellular automata are briefly considered, and connections with dynami-
cal systems theory and the formal theory of computation are discussed.
Reviews of Modern Physics, Vol. 55, No. 3, July 1983 Copyright 1983 The American Physical Society 60i
Wolfram: Statistical mechanics of cellular automata
may instead concentrate on complicated and apparently Cellular automata were originally introduced by von
chaotic surfaces ("strange attractors"). Nearly linear sys- Neumann and Ulam (under the name of "cellular spaces")
tems typically exhibit simple limit points or cycles. When as a possible idealization of biological systems (von Neu-
nonlinearity is increased by variation of external parame- mann, 1963, 1966), with the particular purpose of model-
ters, the number of limit points or cycles may increase ling biological self-reproduction. They have been applied
without bound, eventually building up a strange attractor and reintroduced for a wide variety of purposes, and re-
(typically exhibiting a statistically self-similar structure in ferred to by a variety of names, including "tessellation au-
phase space). A simpler approach (e.g. , Ott, 1981) in- "
tomata, "homogeneous structures, " "cellular structures,"
volves discrete time steps, and considers the evolution of "
"tessellation structures, and "iterative arrays. "
numbers on an interval of the real line under iterated Physical systems containing many discrete elements
mappings. As the nonlinearity is increased, greater num- with local interactions are often conveniently modelled as
bers of limit points and cycles appear, followed by essen- cellular automata. Any physical system satisfying dif-
tially chaotic behavior. Quantitative features of this ap- ferential equations may be approximated as a cellular au-
proach to chaos are found to be universal to wide classes tomaton by introducing finite differences and discrete
of mappings. Notice that for both differential equations variables. ' Nontrivial cellular automata are obtained
and iterated mappings, initial conditions are specifie by whenever the dependence on the values at each site is non-
real numbers with a potentially infinite number of signifi- linear, as when the system exhibits some form of "growth
cant digits. Complicated or seemingly chaotic behavior is inhibition. " A very wide variety of examples may be con-
a reflection of sensitive dependence on high-order digits sidered; only a few are sketched here. In the most direct
in the decimal expansions of the numbers. cases, the cellular automaton lattice is in position space.
Models based on cellular automata provide an alterna- At a microscopic level, the sites may represent points in a
tive approach, involving discrete coordinates and vari- crystal lattice, with values given by some quantized ob-
ables as well as discrete time steps. They exhibit compli- servable (such as spin component) or corresponding to the
cated behavior analogous to that found with differential types of atoms or units. The dynamical Ising model (with
equations or iterated mappings, but by virtue of their kinetic energy terms included) and other lattice spin sys-
simpler construction are potentially amenable to a more tems are simple cellular automata, made nondeterministic
detailed and complete analysis. by "noise" in the local rules at finite temperature. At a
Section II of this paper defines and introduces cellular more macroscopic level, each site in a cellular automaton
automata and describes the qualitative behavior of ele- may represent a region containing many molecules (with a
mentary cellular automata. Several phenomena charac- scale size perhaps given by an appropriate correlation
teristic of self-organization are found. Section III gives a length), and its value may label one of several discrete
quantitative statistical analysis of the states generated in possible phases or compositions. In this way, cellular au-
the time evolution of cellular automata, revealing several tomata may be used as discrete models for nonlinear
quantitative universal features. Section IV describes the chemical systems involving a network of reactions cou-
global analysis of cellular automata and discusses the re- pled with spatial diffusion (Greenberg et al. , 1978). They
sults in the context of dynamical systems theory and the have also been used in a (controversial) model for the evo-
formal theory of computation. Section V considers brief- lution of spiral galaxies (Gerola and Seiden, 1978; Schewe,
ly extensions to more complicated cellular automata. Fi- 1981). Similarly, they may provide models for kinetic as-
nally, Sec. VI gives some tentative conclusions. pects of phase transitions (e.g., Harvey et al. , 1982). For
example, it is possible that growth of dendritic crystals
II. INTRODUCTION TO CELLULAR AUTOMATA (Langer, 1980) may be described by aggregation of
discrete "packets" with a local growth inhibition effect
Cellular automata are mathematical idealizations of associated with local releases of latent heat, and thereby
physical systems in which space and time are discrete, treated as a cellular automaton [Witten and Sander (1981)
and physical quantities take on a finite set of discrete discuss a probabilistic model of this kind, but there are in-
values. A cellular automaton consists of a regular uni- dications that the probabilistic elements are inessential].
form lattice (or "array"), usually infinite in extent, with a The spatial structure of turbulent Auids may perhaps be
discrete variable at each site ("cell" ). The state of a cellu- modelled using cellular automata by approximating the
lar automaton is completely specified by the values of the velocity field as a lattice of cells, each containing one or
variables at each site. A cellular automaton evolves in no eddies, with interactions between neighboring cells.
discrete time steps, with the value of the variable at one Physical systems may also potentially be described by cel-
site being affected by the values of variables at sites in its lular automata in wave-vector or momentum space, with
"neighborhood" on the previous time step. The neighbor- site values representing excitations in the corresponding
hood of a site is typically taken to be the site itself and all modes.
immediately adjacent sites. The variables at each site are
updated simultaneously ("synchronously" ), based on the
values of the variables in their neighborhood at the
preceding time step, and according to a definite set of "lo- ' The discussion here concentrates on systems first order in
cal rules. " time; a more general case is mentioned briefly in Sec. IV.
Many biological systems have been modelled by cellular discussed briefly in Sec. V.
automata (Lindenmayer, 1968; Herman, 1969; Ulam, Until Sec. V, we sha11 consider exclusively one-
1974; Kitagawa, 1974; Baer and Martinez, 1974; Rosen, dimensional cellular automata with two possible values of
1981) (cf. Barricelli, 1972}. The development of structure the variables at each site ("base 2") and in which the
and patterns in the growth of organisms often appears to neighborhood of a given site is simply the site itself and
be governed by very simple local rules (Thompson, 1961; the sites immediately adjacent to it on the left and right.
Stevens, 1974) and is therefore potentially well described We shall call such cellular automata elementary. Figure 1
by a cellular automaton model. The discrete values at specifies one particular set of local rules for an elementary
each site typically label types of living cells, approximated cellular automaton. On the top row, all 2 =8 possible
as growing on a regular spatial lattice. Short-range or values of the three variables in the neighborhood are
contact interactions may lead to expression of different given, and below each one is given the value achieved by
genetic characteristics, and determine the cell type. Sim- the central site on the next time step according to a par-
ple nonlinear rules may lead to the formation of complex ticular local rule. Figure 2 shows the evolution of a par-
patterns, as evident in many plants and animals. Exam- ticular state of the cellular automaton through one time
ples include leaf and branch arrangements (e.g. , Stevens, step according to the loca1 rule given in Fig. 1.
1974) and forms of radiolarian skeletons (e.g. , Thompson, The local rules for a one-dimensional neighborhood-
1961}. Simple behavior and functioning of organisms three cellular automaton are described by an eight-digit
may be modelled by cellular automata with site values binary number, as in the example of Fig. l. (In specifying
representing states of living cells or groups of cells [Burks cellular automata, we use this binary number interchange-
(1973}and Flanigan (1965) discuss an example in heart fi- ably with its decimal equivalent. ) Since any eight-digit
brillation]. The precise mathematical formulation of such binary number specifies a cellular automaton, there are
models allows the behavior possible in organisms or sys- 2 =256 possible distinct cellular automaton rules in one
tems with particular construction or complexity to be in- dimension with a three-site neighborhood. Two inessen-
vestigated and characterized (e.g. , von Neumann, 1966). tial restrictions will usually be imposed on these rules.
Cellular automata may also describe populations of non- First, a cellular automaton rule will be considered "ille-
mobile organisms (such as plants), with site values corre- gal" unless a "null" or "quiescent" initial state consisting
sponding to the presence or absence of individuals solely of 0 remains unchanged. This forbids rules whose
(perhaps of various types) at each lattice point, with local binary specification ends with a 1 (and removes symmetry
ecological interactions. in the treatment of 0 and 1 sites). Second, the rules must
Cellular automata have also been used to study prob- be reflection symmetric, so that 100 and 001 (and 110 and
lems in number theory and their applications to tapestry 011) yield identical values. These restrictions leave 32
design (Miller, 1970, 1980; ApSimon, 1970a, 1970b; Sut- possible "legal" cellular automaton rules of the form
ton, 1981}. In a typical case, successive differences in a a)a2a3a4a2asa40.
sequence of numbers (such as primes) reduced with a The local rules for a cellular automaton may be con-
small modulus are taken, and the geometry of zero re- sidered as a Boolean function of the sites within the
gions is investigated. neighborhood. Let s„(m ) be the value of site m at time
As will be discussed in Sec. IV, cellular automata may step n. As a first example consider the "modulo-two"
be considered as parallel processing computers (cf. Man- rule 90 (also used as the example for Fig. 1}.According to
ning, 1977; Preston et al. , 1979}. As such, they have been this rule, the value of a particular site is simply the sum
used, for example, as highly parallel multipliers (Atrubin, modulo two of the values of its two neighboring sites on
1965; Cole, 1969), sorters (Nishio, 1981), and prime num- the previous time step. The Boolean equivalent of this
ber sieves (Fischer, 1965). Particularly in two dimensions, rule is therefore
cellular automata have been used extensively for image
processing and visual pattern recognition (Deutsch, 1972; s„+i(m) = s„(m —1)es„(m+I) (2. 1)
Sternberg, 1980; Rosenfeld, 1979). The computational
capabilities of cellular automata have been studied exten- or schematically s+ — s Ebs+, where @ denotes addition
sively (Codd, 1968; Burks, 1970; Banks, 1971; Aladyev, modulo two ("exclusive disjunction" or "inequality" ).
1974, 1976; Kosaraju, 1974; Toffoli, 1977b), and it has Similarly, rule 18 is equivalent to s+ — s V (s Ss+ )
been shown that some cellular automata could be used as [where s denotes s„(m)], rule 22 to s+ —— s V(s hs+),
general purpose computers, and may therefore be used as rule 54 to s+ — se(s Vs+), rule 150 to s+ —s @sos+,
general paradigms for parallel computation. Their locali- and so on. Designations s and s+ always enter symme-
ty and simplicity might ultimately permit their im- trically in legal cellular automaton rules by virtue of re-
plementation at a molecular level.
The notorious solitaire computer game "Life" (Con-
way, 1970; Gardner, 1971, 1972; Wainwright, 1971— 1973;
Wainwright, 1974; Buckingham, 1978; Berlekamp et al. , The quiescence condition is required in many applications to
1982; R. W. Gosper, private communications} (qualita- forbid "instantaneous propagation" of value-one sites. The re-
tively similar in some respects to the game of "Go") is an flection symmetry condition guarantees isotropy as well as
example of a two-dimensional cellular automaton, to be homogeneity in cellular automaton evolution.
I I I ) 0 O E
iaaf OII OIO OOI 000 0 I 0 I I 0 I I 0 I 0 I OI I I 000 I 0
0 I 0 I I 0 I 0 00 I I 0 I I 00000 I 0 I I 0 I 0
~ 4
~ ~
8
RUL E 88118118 (S4) RULE 81181eee ( 184 )
9
ie
11
12
]3 ~ ~ ~ s
14 ~ ~
I '5
]6
I ~
~ ~
IB
19
ze
~ ~ ~ ]0
I I
RULE: 81181188 ( 18B )
I
14
I
]6
RuLE: 88818118 ( 22 )
I
]8
]4
28
FIG. 3. Evolution of one dimensional elementary cellular automata according to the 32 possible legal sets of rules, starting from a
state containing a single site with value 1. Sites with value 1 are represented by stars, and those with value 0 by blanks. The configu-
rations of the cellular automata at successive time steps are shown on successive 1ines. The time evolution is shown up to the point
where the system is detected to cycle (visiting a particular configuration for the second time), or for at most 20 time steps. The pro-
cess is analogous to the growth of a crystal from a microscope seed. A considerable variety of behavior is evident. The cellular auto-
mata which do not tend to a uniform state yield asymptotically self-similar fractal configurations.
is nontrivial. In the infinite time limit, the configurations two, as illustrated in Fig. 4 (cf. Wolfram, 1982b). The
are "self-similar" in that views of the configuration with values of the sites are hence the values of binomial coeffi-
different "magnifications" (but with the same "resolu- cients [or equivalently, coefficients of x in the expansion
tion') are indistinguishable. The configurations thus ex- of (1+x)"] modulo two. In the large time hmit, the pat-
hibit the same structure on all scales. tern of sites with value I may be obtained by the recursive
Consider as an example the modulo-two rule 90 (also geometrical construction (cf. Sierpinski, 1916; Abelson
used as the example for Fig. 1 and in the discussion and diSessa, 1981, Sec. 2.4) shown in Fig. 5. This geo-
above). This rule takes each site to be the sum modulo metrical construction rnanifests the self-similarity (Man-
two of its two nearest neighbors on the previous time step. delbrot, 1977, 1982; Cseffen et al. , 1981) or "scale invari-
Starting from an initial state containing a single site with ance" of the resulting curve. Figure 3 shows that evolu-
value 1, the configuration it yields on successive time tion of other complex cellular automata from a single
steps is thus simply the lines of Pascal's triangle modulo nonzero site yields essentially identical self-similar pat-
Rev. Mod. Phys. , Vol. 55, No. 3, Ju)y 1983
606 Wolfram: Statistical mechanics of cellular automata
RULE ' 18888888 (12B) RULE ieiieeie (178) RULE 11811118 (222)
e .
e
I ~ ~ I ~ 0~
2 ~ ~ ~ 2 ~ 0000
0 ~ 0 ~ 3 ~ 0000 $0
4 ~ 0 S 0 ~ 4 ~ 0$000000
5 0 0 ~ 0 ~ ~ 5 ~ 0 ~ 0000000 ~
6 ~ ~ e ~ ~ ~ ~ 6 00 ~ 00 ~ 0 ~ SSS ~ 0
7 ~ ~ ~ ~ ~ ~ ~ 0 7 ~ 0 ~ 0 000 000 ~ 0 00 0
8 0 0 0 0 ~ \ ~ ~ 0 8 000$$$00000000000
RULE : 18888188 (132) 9
Ie
~ ~ ~ 0 ~ 0 ~ ~ ~ ~
~ ~ ~ 0 0 ~ ~ ~ ~ 0 0
9
18
00 ~ 0 ~ 000000000 ~ 0 ~ 0 ~
~ 0$0$00$0000000000000
11 e ~ ~ ~ ~ 0 0 ~ s 0 0 0 Il ~ $$00$$0000000000000000
12 ~ 0 S ~ ~ 0 ~ 0 0 0 0 0 0 12 ~ 0$$$$$$0$0000000000 ~ 0000
13 ~ ~ ~ ~ ~ 0 ~ ~ ~ 0 ~ ~ ~ ~ 13 rs ~ ~ $ ~ ~ SEES ~ 0 ~ 0000000 ~ 00000
14 ~ ~ ~ ~ ~ ~ ~ 0 ~ 0 ~ 0 0 0 ~ 14 ~ ~ EEEsr sssssss ~ 0000000000 ~ $00
15 0 $0
0 0 0 s s s 0 s 0 0 0 ~ 0 15 Eessrssss r $$$0$0$$$000$0$$0000 ~
16 ~ 0 S ~ 0 0 0 0 ~ ~ ~ 0 0 ~ R ~ ~ 16 ~ EE ~ ~ ~ 0 ~ ESESSE~ 0 ~ 0 ~ 0 ~ 0 ~ 0$0$ ~ S ~ EOE
17 0 ~ ~ ~ ~ ~ ~ ~ 0 ~ 0 ~ ~ ~ ~ ~ 0 0 17 ~ ~ ssees ~ ess ~ esss ~ Eeee00000ee0$0 ~ Sss
18
19
0 ~ ~ ~ ~ ~ ~ ~ ~ ~
\ 0 S 0 E 0 s 0 s 0 E
18
19
000 F 00
~ 0\$0 ~ 00 ~ 0$0 ~ ~ 0 ~ ~ ~ 0 ~ 000000 ~ 00 ~
$0$$$$ ~ 00$$00 ~ 0 ~ $0 ~ $000$ ~ ~ 0 ~ 000$00000$0
'
28 ~ ~ S S S ~ S ~ ~ E ~ $ ~ ~ S ~ ~ S ~ ~ ~ 28 ~ 0 ~ 0 ~ 0 ~ 0 ~ 00$00
~ SEE ~ 0 ~ $$ ~ ~ 0 ~ SS ~ 0$ ~ $0 ~ 0 ~ E ~ 0
II ~ E ~ $ ~ S 0$$
12 5
6 E S S ~ 0 0
l3 ~ ~ 0 ~ r ~ ~ 0
0 0 ~ 0 7 ~ ~ ~ ~ ~ ~ E ~ 0 ~ ~ s ~ ss
I~ ~ ~ ~ ~
8 ~ ~ ~ ~ ~ 0 ~ ~ 0$ ~ sss ~
15 ~ 0 ~ ~ ~ $$ ~ ~ 0 ~ ~ s ~ ~ ~ ~
Ii 9
17 s ~ le 0 ~ ~ ~ ~ ~ ~ ~ e ~ 0~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ E ~ E~ ~ ~ ~ 0~ ~ 0 ~ ~
RULE: 11 181 188 ( 236 )
Ie . ~ s 11
r 12 0 ~ S ~ ~ ~ ~ ~ ~ ~ 0$ 0 ~ 0 ~ ~ ~ S
19 ~ ~ ~
s ~ ~ ~ ~ ~ ~0 ~ ~ ~0 0~ ~ ~ ~ ~ ~ ~r
ze 13
14 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~
15 sr ss $$$$0$$$$$$ ~ 0$0$$$ esse esses
16 0 0 0 SSS S $$$ $$$ ~ E S E ~ E ~ E ~ S ~ ~ SRS 0
I7 s ~ sr 0 s see ~ s $ 0 0 s 0 0 0 SSSSES~ $0 $0$
16 s r 0 ~ sssssssesss ~ ssese ~ eeosss 0 0 ~
19 ~ ~ ~ ~ ~ ~ r ~ ~ r re ~ ~ ~ sr s ~ 0 ~ ~ ~ s0ss0 sr ~ 0 ~ ~ ~ 0 ~
2e ~ ~~ r ~0 ~ ~ ~s ~ ~ ~ ~ r ~ ~ ~ ~ 0~~0~s~ ~~ ~ ~ 0~ ~0 ~
4 ~ 0 ~ ~ ~
5 5 ~ 0 0 0 0
6 6 0 0 ~ \ 0 0 0
7
RULE -' 1 1881888 ( 288 ) ~ 0 E 0 ~
8 ~ ~ ~ 0 0 0 0 0 E
9 r ~r ~ ~~ ~ ~ r
9 0 0 0 ~ 0 0 0 ~ 0 ~
Ie ~ ~ s ~ S ~ ~ ~
18: 0 S ~ ~ ~
I I 0 \ 0 ~ 0 0 0
IZ 11
~ ~~
~ ~ ~ ~ ~ 0 ~ ~ ~ 0 ~ ~ 0
I 3 ~ ~ ~ 0 ~ 0 ~ ~ ~ ~ ~ ~ ~ ~
14 ~ 0 r 13
c I~ 0 0 0 0 ~ 0 ~ 0 ~ ~ 0 0 ~ 0 ~
I
15 0 0 0 ~ 0 ~ ~ ~ 0 0 ~ ~ 0 0 ~ 0
l6 '16 ~ ~ 0 ~ ~ 0 0 0 0 ~ 0 0 ~
s sr ~ rr re ~ 0 ~ 0 0 0 0 ~ 0 0 0 0 ~ 0
s r r s r r r
16
19 ~ ~ ~ ~~ r~
~
~ ~ r ~~
S
~ r~ 18: 0 ~ ~ 0 ~ 0 ~ ~ 0 ~ 0 0 ~ 0 ~ 0 ~ 0 0
I
2e 19 ~ 0 0 ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~
2e ~ 0 0 0 0 ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ E 0 ~ ~
RULE '- 1 1881 188 ( 284 )
RULE: ie 1 88888 ( i 68 )
RULE 11111118 (2S4)
1 iei i 8ie ( 218) I ~ 0$
e 2 eo ~ 0 ~
I ~ ~ 3 ~ 0$ ~ 0 ~ 0
2 0 &0000 ~ Oss
3 ~ ~ r 0 E 0 0 O '0 0 0 0 E E E
4 6 ~ 0 ~ 000000 ~ SE ~
RULE: ie i 88 1 ee ~ ssesesse ~ esses
( 164 ) 5
6 8 soRE ~ ~ 0$ ~ 0 ~ 0 ~ E ~ ~ E
7 9 0 ~ 0 Es ~ ~ 0$ 00 0 ~ s ~ E ~ 0$
6 fe 0$$0$0$00$00000 ~ $0000
11 ~ Essrr E\s ~ $0000 ~ $0 ~ Sess
le 12 '
~ e ~ s 0 ~ $ 0 ss 0 00 ~ ~ 0 E ~ 00 o E 0 0
11 13 ~ 0 ~ Os ~ S 0 ~ S ~ $0 ~ S ~ 0 ~ ~ 0 ~ O ~ $$ ~ 0
12 14 Esse ~ 0 ~ 0 ~ sss ~ $0 ~ 00$ ~ 0 ~ ~ ~ 0 ~ 0 ~ 0
13 ~ ~ 15 ~ 0 ~ ss ~ ~ ~ ~ ~ 0 ~ ~ 0$$$0$ ~ ~ oss ~ 0 ~ 0 ~ os
}4 s 0 s 0 16 0 0$ ~ 0 r 0 ~ \ sr 0 s ~ ss ss\0$ 0$ E sss'0 $$ ~ s ~
15 r s ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ S ~ 0 ~ ~ 0 ~ ~ ~ ~ ~ s ~ ~ sr ~ E ~ s ~ 0 ~ 0000 ~ 0 ~ 00 ~
I
16 18 $$ ~ 0 ~ S ~ 0 ~ RS ~ s ss 1$ ~ ~ e Es ~ 0 ~ ~ 0 ~ SSS~ 0000 ~
17 s 19 ~ ~ sr $$' ~ ~ r ~ ~ ss ~ ~ ~ ~ $0 $0 ~ 0 ~ 0$$00 ~ ss ~ 0 ~ 0 $00
16 28 ~ ~ r s sr 0 s see ~ ~ 0 0 ~ ~ ss ~ s 0 ~ ~ 0 0 ~ 0 ~ sos 0 0 ~ ~ s ~ ~ 0 ~
19 0 E ~
ze
I
«ms. An exception is rule 150, for which the value of
I I each site is determined by the sum modulo two of its own
2 I
I 5 IO IO 5 I
I 6 20 I5 6
I5 I
lution from a single-site initial state for n time steps with
7 2I 35 35 2I 7
this rule is thus simply the coefficients of x' in the expan-
I
/,
h —V
I
FIG. 5. Sequence of steps in a geometrical construction for the FIG. 6. Sequence of steps in a geometrical construction for the
large time behavior of a cellular automaton evolving according large time behavior of a cellular automaton evolving according
to the modulo-two rule 90. The final pattern is the limit of the to the modulo-two rule 150. The final pattern is the limit of the
sequence shown here. It is a self-similar figure with fractal di- sequence shown here. It is a self-similar figure with fraceal di-
mension log23. tnension log&29/=1. 69 [where y=(1++5)//2 is the golden ra-
tio]. An analogous construction for rule 90 was given in Fig. 5.
shifting. The self-similar patterns seen in Fig. 3 are also are identified, as if they lay on a circle of finite radius.
found in cases such as rule 225, but are sheared by the Cellular automata can also be rendered finite by imposing
overall shifting. It appears that consideration of illegal as null boundary conditions, under which sites beyond each
well as "legal" cellular automaton rules introduces no end are modified to maintain value zero, rather than
qualitatively new features. evolving according to the local rules. Figure 9 compares
Figure 3 showed the growth of patterns by cellular au- results obtained with these two boundary conditions in a
tomaton evolution from a very simple initial state con- simple case; no important qualitative differences are ap-
taining a single nonzero site (seed). Figure 8 now illus- parent.
trates time evolution from a disordered or "random" ini- Finite one-dimensional cellular automata are similar to
tial state according to each of the 32 legal cellular au- a class of feedback shift registers (e.g. , Golomb, 1967;
tomaton rules. A specific "typical" initial configuration Berlekamp, 1968). A feedback shift register consists of a
was taken, with the value of each site chosen independent- sequence of sites ("tubes" ) carrying values a(i ). At each
ly, with equal probabilities for values 0 and 1. Just as in time step, the site values evolve by a shift a(i)=a(i —1)
Fig. 3, several classes of behavior are evident. The simple and feedback a(0)=F[a(j~ ), a(j2), . . . ] where, j; give the
rules exhibit trivial behavior, either yielding a uniform fi- positions of "taps" on the shift register. An elementary
nal state or essentially preserving the form of the initial cellular automaton of length N corresponds to a feedback
state. Complex rules once again yield nontrivial behavior. shift register of length N with site values 0 and 1 and taps
Figure 8 illustrates the remarkable fact that time evolu- at positions N — 2, N —1, and N. The Boolean function F
tion according to these rules destroys the independence of defines the cellular automaton rule. [The additive rules
the initial sites, and generates correlations between values 90 and 150 correspond to linear feedback shift registers in
at separated sites. This phenomenon is the essence of which F is addition modulo two (exclusive disjunction). ]
self-organization in cellular automata. An initially ran- At each shift register time step, the value of one site is
dom state evolves to a state containing long-range correla- updated according to the cellular automaton rule. After X
tions and structure. The bases of the "triangles" visible in time steps, all N sites have been updated, and one cellular
Fig. 8 are fluctuations in which a sequence of many adja- automaton time step is complete. All interior sites are
cent cells have the same value. The length of these corre- treated exactly as in a cellular automaton, but the two end
lated sequences is reduced by one site per time step, yield- sites evolve differently (their values depend on the two
ing the distinctive triangular structure. Figure 8 suggests preceding time steps).
that triangles of all sizes are generated. Section III con-
firms this impression through a quantitative analysis and
III. LOCAL PROPERTIES OF ELEMENTARY CELLULAR
discusses universal features of the structures obtained.
AUTOMATA
The behavior of the cellular automata shown in Fig. 8
may be characterized in analogy with the behavior of We shall examine now the statistical analysis of config-
dynamical systems (e.g. , Ott, 1981): simple rules exhibit urations generated by time evolution of "elementary" cel-
simple limit points or limit cycles, while complex rules lular automata, as illustrated in Figs. 3 and 8. This sec-
exhibit phenomena analogous to strange attractors. tion considers statistical properties of individual such
The cellular automata shown in Fig. 8 were all assumed configurations; Sec. IV discusses the ensemble of all possi-
to satisfy periodic boundary conditions. Instead of treat- ble configurations. The primary purpose is to obtain a
ing a genuinely infinite line of sites, the first and last sites quantitative characterization of the "self-organization"
pictorially evident in Fig. 8.
RULE: 88888881 ( i)
1
8 2
1 eeeeeeeeeeee¹eeeeeee eeeeeeeeeeeeeeeewee 3 e I¹
2 ~
I4l
4 Iil ¹ ¹
5 I4l e ¹
'lil
6 ¹
14 e
5 15
k6
I4l ¹ e e
Iil '¹ e I4l lil
Ill e
7 ~
e I4l e e e I4f Iil ¹ e
8 iB e e e e
9 I4I
¹»
l4I Iil lil
19 e e e e e
\8 28 e
¹ ¹ ¹
11 ¹ ¹
12
13
14
15
16 RULE : 888iiii8 (38)
17 8
1B 1
19 2
28 3
4
6
RULE 8888%Bi K ( 1i ) 7
B
¹¹¹¹
9
8 18
1 11
12
3 13
5
6
e¹eeeee¹e¹¹e¹¹¹¹¹¹el4¹e¹e¹
«eeeeeeeeeee¹ee 14
15
16
7 ~
17
B lB
9 e e ee e ee e ee e ee e eee'ee ¹ ee e ee e e e e e ee ¹ e'¹eee e e 19
18 I4I e 28
11
12
13
14
15
16 RULE: 11188881
17
1B
19
28
8
2
3
eeeeeeeeeeeeeee¹¹¹¹¹
eeeeee¹eeee¹eeeeeeee
e e e e e e e 'e e e e e e e e e
l4l
e
eeeeeeeeeee¹ee¹ ¹
¹e¹e¹e¹e¹e¹¹¹¹¹
ee¹eee¹ee¹ee¹e¹¹¹e
¹e
e e e e e ee e e e e e I¹ ee e e e I4ll¹ e ¹I e
~ ¹
ee ee e
5
l4l
'¹
ee'¹e e'e e e'¹'e'ee e ee e ee e e e
¹ ¹ ¹ I4l ¹
e e ee e e'ee e e e e
¹ ¹
'¹¹e¹eee¹eeeeee¹
¹e
¹ ¹ ¹
¹¹¹¹¹¹¹¹¹¹¹¹
¹ ¹
6 e e e e e e e e e e e e el4l e e e
l4l l4l ¹
Il 4l e e e e
¹ eeeee ¹ ¹ ¹
e e e e e e e e e e e e 'e e e e e 'e e e e
RULE 88881 181 ( 13) 7
¹¹¹¹¹¹e¹¹¹
¹ ¹
"-
e e e e e e e e e e e e e ee e e e e e eeee ee
B
'¹ e¹
¹¹¹¹'¹¹¹¹¹¹¹¹¹'¹¹
e e e e e e e e e e Ill e e III I¹e Iil I¹ e e e
¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹
e I¹e e e
¹
9 ~
l4l l4t I4l I4l I4I I4l ¹ ¹ ¹
18 el¹eel4ll4l¹lil¹el4lel4II4ll4le'e'¹el4II4l¹eee ee e ¹elileeel¹ee¹
i eeeeeeeeeee¹eeee¹¹'¹ee eeeeeeee'¹¹ee'¹eee¹'¹¹ 11
2
eee¹eeeee¹¹ee¹¹¹¹eee
e e eee¹eeeeeee¹ee¹¹¹
12 eeee¹¹eeeeeee¹ee¹eeee¹e¹ee¹
e «e eeeee¹ee
¹¹¹e¹¹¹¹¹
3
4
13
14 eellleeee¹¹I¹e¹¹¹¹¹¹¹'¹e¹¹¹¹e¹¹¹¹
e e lil e e
'¹ e¹lil¹e¹
I4l ¹ ee ee ¹ ¹ ¹ lil ¹ III ee ¹ Ill eeee I4t ¹ e ¹ I4l
Ill
ee e e ¹ ¹ III
e¹e¹eee¹e¹eee¹¹¹¹¹e¹ee¹*¹¹¹¹¹¹
¹
5 eeeee e e
¹.
15 ¹ I4l ¹ I4l ¹ 4l Iil ¹ ¹ ¹ ¹ ¹ ¹ ¹ e ¹ lil ¹ l4l I4l lil ¹
6 16
7
B
9 ¹ee¹eeeeeeee¹¹¹¹¹¹¹¹ III elise el'¹Iil
17
1B eeeeeee e e e
e lk e e e e ee
'¹ '¹ e e e e ¹ ¹ ¹ ¹ lOL
e
¹
e
¹
¹
lIL
¹
¹
eee
¹
e e e I¹e Iil
eeee eee
¹
¹ ¹ ¹ ¹ ¹
Iil ¹ ¹ ¹ lil
19
eeee¹¹¹ee¹¹ee¹¹¹eeeeeeee¹¹¹¹»ee¹¹¹
¹ ¹ ¹ ¹ ¹¹¹¹
¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹
18
¹ ¹ ¹ ¹
'¹ 28 ee ee
11
12
13
14
15 I4I¹ lil¹l4l¹¹ l4l ¹lil¹lil¹lil lil
¹
¹
¹
¹
¹
i/I
¹
¹
¹
lil
¹
¹ ¹
¹
e¹e¹¹¹¹
I4f¹¹l¹¹
: 111ii.iii
¹¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹
16
17 ¹ e ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹¹¹ RULE (255)
1B ¹ ¹ ¹
19 ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹
8
28 4l ¹ ¹ ¹ IO ¹ ¹ ¹ l4I ¹I ¹
FIG. 7. Evolution of a selection of one-dimensional elementary cellular automata obeying illegal rules. Rules are considered illegal if
they violate reflection symmetry, which requires identical rules for 100 and 001 and for 110 and 011, or if they violate the quiescence
condition which requires that an initial state containing only 0 sites should remain unchanged. For example, rule 2 violates reflection
symmetry, and thus yields a uniformly shifting pattern, while rule 1 violates the quiescence condition and yields a pattern which
"flashes" from alll 0 to all 1 in successive time steps.
A configuration may be considered disordered (or at different sites. An (infinite) disordered configuration is
essentially random) if values at different sites are statisti- specified by a single parameter, the independent probabili-
cally uncorrelated (and thus behave as "independent ran- ty p for each site to have value l. The description of an
dom variables" ). Such configurations represent a discrete ordered configuration requires more parameters.
form of "white noise. ' Deviations of statistical measures Figure 10 shows a set of examples of disordered config-
for cellular automaton configurations from their values urations with probabilities @=0.25, 0.5, and 0.75. Such
for corresponding disordered configurations indicate or- disordered configurations were used as the initial configu-
der, and signal the presence of correlations between values rations for the cellular automaton evolution shown in Fig.
Ie
CO )
oo ~
bo 'g
5
~ 4 ~ ~ ~
5 ~
4 5 0 5 ~
~ S a
~ ~
0
4 4 0
5 5
5
0
~ 0 0
~ 0
5
~
0 0
0 4 ~
~
5
~ 5 0
0
~ ~
0 ~ 4
0
0 0 0 0
8 0
4 4
0
5 5
a
~ ~ 0 0 ~
~ ~ ~ ~
0 0 1 4
0 4 0 0
0
0
5
0 0 0 4 1 0 0 ~ g
~ ~ ~ ~ ~ ~ ~ ~ ~ V7
5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ 4
0 ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ESS ~ Pse
4 ~ ~
~ ~ ~ 0 0 0
~ ~ ~ ~ ~ 0 ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
g$
0
~
~ ~ 0
~ ~
4
~
~
0 ~
~ ~ ~ ~
0
0~ ~ ~ ~
~ ~
~ ~
~ ~
~ ~
0 ~ ~
~ ~
~ ~
~ ~
0 ~
~
~ ~ ~
~ ~ ~ ~
0 ~ ~ 4
~ ~ ~ ~ ~
~ ~ ~ 0 ~ ~
C
esS
~ ~ ~ ~ ~ 1 ~ ~ ~ ~ 0 ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4
~ ~ 4 ~ 0 0 ~ ~ ~ ~ ~ ~ 0 ~ 0 ~ ~
~ ~ ~
~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ 0 ~
~ ~ ~ ~
~ ~ 4 ~ ~ 0 ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ CA
0 ~ ~ 4 0 0 ~ ~ 0 ~ 0 ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 4
~ ~
~ ~ ~ ~
~ ~ ~ ~
~ 4 ~ ~
~ ~ ~
0 ~ ~ ~
4 ~ 0
0 ~ ~ ~ ~ ~ ~ ~
~ ~ 0 ~ ~ ~ 0 ~ ~ ~ ~
~ ~ ~
~ ~ ~
~
~ ~ ~ ~ ~ ~ Q
~ ~
0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4P
~ ~ ~ ~ 4
4 ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~
~ ~
~
0 ~
~
~
a ~ ~ ~ ~ ~
~ ~
~ ~
0 ~
~ ~ ~
~ ~
~ ~ ~ 0
~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Q
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
0 4 ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 1 0
~
~ ~ ~ ~ 0 ~ 0
~ ~ ~ 0 ~ 4 ~ ~ 5 ~
~ ~ ~ ~ ILJ
~
0 0 ~
~
4
0 ~
II
~ ~
~ ~
0
0 ~ ~
~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~
4 ~ ~
~ ~
~ ~
~ ~ ~ 0
~ ~
~ ~ ~ ~
~ ~ ~ ~
0
0
~ ~ ~
~ ~ 0
~ ~
~ ~ 0 0 0
~ ~
~ ~
~ ~
~ ~
~ ~ ~
~ ~
~ ~ ~
~ ~ ~
~
~ ~ ~ ~ ~ ~ 0 ~
~ ~ ~ ~ ~ ~ 0
~ ~ 0 ~ ~ 0 ~ ~
o cA
~ ~ ~ ~ ~ ~ ~ 0 ~
0 ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 0
~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~
~ 5 ~ 5 ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ 0 ~
0 ~ ~ ~ 0
o E
~ ~ ~ ~ ~
0 ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ 5 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
0 ~ ~ ~ ~ ~ 0~ ~
~ ~ 1 ~ ~ ~ 0 ~ ~ ~ ~ ~ 0 ~ ~ 5 ~ 0 ~ 0 ~ ~ ~
~ ~ ~ ~ ~ 0 ~ ~
~ 0 5 0 0 ~ ~ 4 ~ ~ ~ 0 ~ ~
~ ~ ~ 5 4 05 0 ~ 0 4 5 0 0 ~ 0 0 0
~ ~ ~ 0 ~ 4 4 0 4 4 0 0 ~ 0 0 0 ~ 0 5 0 0 ~ 0 0 0
e 0 ~ ~ 4 ~ ~ 4 5 4 0 E
~ ~ ~
4
0 4
~ ~
0 ~
~ ~ ~
1
~ ~
~ 4
4
~ ~
~
~
~
4
~
~ ~ ~
~ ~
0 0 ~ 0 4 0
0 ~
0 ~ ~ ~
~ ~ ~ ~ ~ ~ 0 ~ ~ ~
Q
~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
I9 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~
~ 5
~ ~
lD ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ I9 ~ ~ ~ ~ ~ ~ ~ ~ ~
I9 ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ Al ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ AJ
~ ~ ~ ~ ~
4 ~ ~
~ ~ ~ ~
~ ~ ~
~ ~
~
~
~
~ ~
~ ~ ~ ~ ~
~ ~
~ ~
1 ~ ~
SV ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~
0
~ ~ ~ ~
C6 bo
~ ~ ~ ~ ~
1 4 ~ ~ ~ ~ 4 ~ ~
4 ~ 1 ~
5 ~ ~ ~ ~
~
~
~ ~ ~
~ ~
~ ~
~ 0 ~ 0
~
~
~ ~ ~
~
~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ O
~ ~ ~ ~ ~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ 5
4 ~ ~
~ ~ ~ 0 ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~
~
~
~
a5
4 F IQ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ 1 ~ ~ ~ ~ ~ ~ 0 0 ~ ~ ~ ~ ~ ~ ~
0 ~ ~ ~ ~ ~ ~ 5 ~ ~ ~ ~ IQ ~ ~ ~ ~ ~ ~ ~ ~ ~ 1
~ ~ ~ ~ ~ ~ ~ ~ 0 ~ 0 ~
0 ~ ~ ~ ~ ~ ~ ~ 1 ~
~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~
IQ ~ 0 ~ ~ 4 ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ee ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ 4 ~ ~
1 ~
~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ 0 ~ ~
~
~ ~
~ ~
~ 0 ~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~ IQ aS
~ ~ ~ ~ ~ ~ ~ ~ 5 ~ 5 ~ 0 ~ ~ IQ 0 ~ ~ ~ ~ ~ ~ ~ 0 ~
~ 5 5 4 5
~ ~ ~ ~
4 ~ 4 5 4 04 ~ 4
~
5 0 ~ ~
~ ~ ~ ~
~ ~ ~ ~ 5 ~ ~
~ ~ 0
~ ~ IQ 0 a$
4 ~ 5 5 E ~ ~ 0 5 0 4 4 4 ~ ~ 0 ~ 4
4 4 5 5 ~ ~ ~ e ~ 4 4 0 4 0 4
~ ~ 5 4 ~ ~ 4 ~ ~ ~ ~
0 ~ e ~ 0 ~ 5 ~ 0 ~ 5 ~ ~ ~ ~ 0 ~
IQ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~
~ 4 ~ ~ 0 ~ ~ ~ ~ ~ ~
O
4J 4J s —n. r, 1 4' D r. m 0 m ~1
rr ~ 5 D I m 0' sl v m r m o m
tlt III ttl SI hl ltt tll 0& tlt rv Pl
LEJ
a al pt ~ st g r. m Sl PI ~ st tar cl m 0 ltl pr~ sr &D r. m 0& m 4J
m rtl
D
m m sr re al st lit rs Ie sl SI Ilv pl m rttplratmr. 0 alp&% sr&85
K R
cA
cA
o bo
g
~ 4 ~ ~ ~ ~ ~
6
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~
~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~ ~
~ 4 ~ ~ ~ ~ ~ CP
~ ~ ~ ~ 0 ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
0
~ ~
~ ~
~
~ ~
~
~ ~
~ ~
~
~ ~
~ ~ ~
~ ~ a 0 ~
~ ~ ~
~ ~ ~
~ ~
~ ~ ~
~
~ ~ ~
~ ~
~ ~
~
~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
o P
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
5
0 ~
~ ~
~
~
~ 0
~
4
~
~
~
~ ~
~
~
~ ~
~
~ ~ 0
~ ~ ~ ~ 0
~ ~ ~ ~ 0 ~ ~ ~ ~ ~
~ ~
~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~
~ ~ ~ Q rh
~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ 0 ~ ~ ~ 0 ~
~ ~ ~ ~ ~ ~ ~ 0 ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ q5
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
0
~ ~ 0
~ ~
5
~ ~
~ ~
~
~
0
~
~
~
~
~
~ ~
~ ~
~ ~
0
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ 0 ~ ~ ~
~
4 ~
~
~ ~
~ ~
~ 0
~ ~ ~
~ 0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~
0 ~ 0 0 ~
~ ~ ~ ~ ~ ~
~ 0 0 4 ~ 0
o o
5
5 0
~ ~
0
0 5
~ ~
~ 0
0
~
~ ~
~
~
~
~ 4
~
~
~ 4
E
S ~
0
~
0
~
0
~
~ ~ ~ ~ ~ 0 ~
4 0 ~ 0
0
0
4
0
0 0
~ ~
~ ~
~ ~
~ 0 0 0
0 ~
4 ~ ~ 0 0
~ ~ ~ ~ 0
0
5 0
0 ~ 5
~ ~
~
~
0 ~ 0
~
0 ~ ~ 0 ~ ~ ~ ~
4 0 ~ ~ ~ ~ ~ ~ ~ ~ ~~
~ 0 0 ~
~ ~ 4
~ ~
c6 q$ o
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 4
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
0 ~
~
~ ~
0
~ ~ ~ ~ ~
~ ~ ~ 0 ~ ~ ~
~ ~
~ ~
~ 0
~ ~
~ ~ ~ ~
~ 0 ~
0 ~
~ ~ ~
~
0
~
~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 0 ~ ~ ~ 0
0 ~ ~
1 ~ ~ 0
~ O
~ 0 ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 ~ 0
~
~ ~
~
~
~
~
~
~ ~
~ 4
5
~
~
~ ~
~
~ ~
~ 0
0 ~
~ 0
~ 4
~
4
~
~ ~
~ ~
a
~
~ ~
~ ~
~ ~
~ ~
~ ~
~
~
~ 0
~ ~
~ ~ ~
~ ~
~ ~ ~
~ ~
~
~
~
~ ~
~ ~
~ ~ ~
~ ~
~ ~
~ ~
~ 0 ~
~
~ 0 ~ ~ ~
~
~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~
0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ 0
~ ~ 0
~ ~ ~
~
~
~
~ ~
~ ~ ~
~ ~ 0 ~
~ ~ ~
o
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~ 0
~
~ ~
~
~
~ ~
0
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~
~ ~
0
~ ~ ~
0 ~ ~ ~ ~ 0
~ ~
~ ~
~ ~ ~ ~ ~ ~ O
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ 0
~ ~ ~ ~ ~ ~
~
~ ~ AJ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ IQ
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ a5
4 ~ ~ ~ gL ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ 0 ~ 0 ~ ~ ~ ~
~ ~
~
~ ~
~ ~ ~
~ ~
~ ~
~
5 ~
~
~
~
~
~
~ ~
~ ~
~
~
~
~
~ ~ 0 ~
5
~ ~ ~
~ ~ 0 ~
~ ~
~ ~ ~
~ 5 ~ ~
~ ~ ~
~ ~ ~
~ ~
4
~
~
~ ~ ~ ~ ~ ~ 0 ~ ~
bo
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
"o0
~ ~ ~ ~ 0 0 ~ ~ ~ ~ ~ ~
IQ
~ ~
~
~ ~
~ ~ ~
~ ~
~ ~
~
~ ~
~
0
~ ~
5 ~
~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
0
~ ~
~ ~ 0
1
~ ~ ~
~ ~ ~
~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
0 ~ ~
~ ~ ~
~ ~
~ O
~ ~
5
5 ~
1 0
~ ~ 5 5 5 5 e IQ 0 1 I9 ~
~ ~ ~ 0 4 5 '5 ~ ~
~ ~
0 5
0 IQ ~ 5 0 0 0 0 ~ 0 4 1 ~ 0 0
47 0 a$
4
~
5
~ ~ 4 5 E ~ 4 I9 4 ~ E 0 ~ 0 ~ 4 4 0 0 ~ 4 4 4 0
~ 0
0
~ ~
~ ~ ~ ~
E
4
~ ~ ~ ~
5
~ ~
I9 ~ ~ ~ ~ ~ ~
E
4 ~ ~
5 ~
~ ~ ~ 0 4 ~ ~
~ ~ ~ 0
~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~ ~ ~ ~ ~
~
~
~
~
~
~
~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
Il
%5
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~
~ ~ 4 ~ a ~ ~ ~ ~ 0 0
~
~
~
~
~ ~
~ ~
~ ~
~
~ ~
~
0
~
~ ~ IQ C9 ~ ~ ~
~
~ ~
~
0 ~ ~ ~
0
~
~ ~
~ ~ ~ ~ ~ ~ 0
~ ~
~ ~ ~ ~ 0 ~ ~ ~ 0 I9
~ ~ ~ ~ ~ ~ ~ ~ ~
~ IQ IQ IQ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ IQ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~
IQ ~ ~ ~ 0 5 ~ ~
~ ~ ~ ~ ~ 4 ~ 5 ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
IQ IQ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I9 ~ ~ Cl
Q
bG
4J
~' D &a
m- ~ ~ ~ W Dr mern-r.
hJ
~
II r & ~
~ v.
I& m
Dr mamp&
I I &'
m
4J
m n, m
4J
J
4J
0 stpl 1 stgr. ms&
Pl I' m 0& m
ltr tlr
Elm ~ a&mr me&m
te re st at al le III Ie PI J
4J
m IIIPI ~ SI &8 r- m
al PI J
4J
m ~ Ie rs ~ 0& m e
a m
Q
I. '
IZ R IL
g v)
55
o
O ~ C
C$ M
I/) bo OJ
o
~ ~ ~ 0 ~ ~ ~ ~ ~ 0
~ ~
~ ~ ~
~
0
~
~
~
~ ~
0
0
~ ~
~
0 ~
~ ~ ~ ~
0
~
~ ~
~
4 0 ~
~ ~ Q
0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ el)
5 ~ 5 ~ 5 \ ~ ~ E
1 4 ~ 5 ~ 0 ~ ~ 0 ~ 0 0
0 0 5 0 0 ~ 5 0 ~ 0 ~ ~ 8 4 0
0
~
~
~
~
~
~
~ 4 ~
~ ~
~
~
~ ~
~
4
~ ~
~ ~
4
0
~ ~
~
~ ~
a 0
0
~
~
0
~
af ~
*~ ~ O
~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~
~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
0 4 0 ~ ~ ~
~ ~ ~ ~ ~ 0 ~ ~ ~ 1 ~ ~ 0 ~ ~ ~ 0 ~
~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
1 4 ~ ~ CCS
~ ~ ~ 0 ~ ~ ~ 5 ~ ~ ~ ~
~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~ ~ ~ ~ ~ ~ 0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
0
4 ~ ~ ~ ~
~ ~
~ ~
~ ~
~ ~
~
~
~ ~
~
~ ~
~
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~ ~ 0
~ ~
'Q .~ O
~ ~ ~ ~ 0 0 ~
~ ~ 0
~ ~ ~ ~
~ ~
~ ~
~ ~
4 1
0 ~
~
~ ~
~
~
~ ~
~ ~
4
a5 Z0 a5
~ ~ ~ ~ ~
~ ~ 5 5 ~ ~
~ ~ 4 ~
~ ~ ~ ~
~ 0 ~ ~ ~ ~
~
~
4
~
~
Q Isel
~ ~ 5 a5
~ 0 0
4
0 ~
0
~ 4
5 5 ~ 0 4
~ ~ ~ ~
0
~ ~
0
4
~
0
~
4
~ a ~ 0
0
0
~
0
~
4
~
Q
E E 5 0 4
5
0 E E E ~ 0 ~ 0 ~ 5 4 4 0 0
4 ~ 0
0 4
~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ 0 ~ 4
~ ~ ~ 0 ~ ~ ~ ~ ~ ~ CV 1 ~ ~
~ ~ 5 ~ Iel ~ ~
~ ~ ~ ~ 5 ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ 4 ~ ~
0 ~ ~ 5 ~ 5 ~ ~ ~ ~
0 ~ ~ ~ ~ ~ ~ ~
~ 4 ~ ~ ~ ~ 0 ~ ~
IQ CQ ~ ~ 0 ~ ~ ~ ~ ~ ~ IQ ~ ~
~ ~ 5 5 4 ml 0 ~ 4 ~ ~ 5 ~ ~ ~ ~ ~ 0
IQ IQ we
~ ~ 5 ~ ~ ~ ~ ~ ~ ~ ~ IQ ~ ~
I9 ~ IQ ~ ~
~ ~
~ ~ ~ ~
54 ~ ~ 5
I9 ~ ~
~ ~
IQ ~ IQ 6l 5 5 ~ ~ 5 0 ~ ~ ~ IQ ~ ~ ~
IQ ~ ~ ~ ~ ~ ~ ~
IQ ~ ~ ~
IQ ~ ~ ~ ~ ~ ~
5 ~ ~
I9 5 5 ~ ~
IQ IQ 4 I9 ~ ~ ~ ~ ~ ~
0 0 ~
~ ~ ~ E ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
IQ IQ IQ IQ S ~ ~ 5 5
IQ IQ IQ ~ 5 5 0 5 IQ ~ ~ ~ ~ Cl 0 0
~
O
J
4J
m
4J
J
4J
m &F Pl ~ Vl &It I m
r~ pt 4 SI m t. m 8 el
tent
rt w 0 v D
I rt &It 5«
5 t&t «
I m
&t
0
t'4 Pt
4I
0 tt pl 1 4 4 ~'
I Pt '4 am~ &~P& ~ &ID& laa
It n, re rs r& r&t m t&t rt tent
pl J
4J
~ rtt pl 8
4J
D
J
4I
m IIIPIe St&Dr m
I9 .~ .2
0'. R R R
O
ca
c
cj O
cil OJ
Q ~'g tt)
ca o O
~ a ~ I ~ ~ ~ ~
4 I ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ 0 P 0
~ P ~ ~ ~ ~ 4 0 ~ ~ ~ 0 ~
~ ~ ~ ~ ~ 0 ~ ~ ~ 0 0 ~ ~
~ 0 ~ 0 ~ 0 ~ ~ ~ ~ ~ 0 0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ a
~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
~
~
I~ I~ 0
~
0 ~
~ h ~
~
I I~~ ~ 0 0
~ ~ ~
~
~
~ 0 ~ ~ ~ ~ ~ ~ 0 0 ~ 0 ~ ~
0
~ ~
I 0
~
0 ~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~
I ~
~
~ ~ ~
~ ~
~
~ ~ I 0 0 ~
~ ~
~ ~ ~ 0
0 0 ~ I ~
~ ~ ~
~ ~ ~ ~ ~ ~ P ~ ~ ~ ~
I ~ ~ ~ 0 ~ ~ 0 ~
~ ~ ~ ~
~
~
~ ~
0 ~
~ ~ ~ 0 ~ ~ ~
0 ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ 4
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ 0 4
I
~
0 ~ ~ ~ ~
~ 0
~ ~
~
~
~ ~ ~ ~
~ ~
~ ~ 0 ~ 0 ~ ~
~ ~ ~ ~ ~ 0 ~ ~
~ ~ ~ ~ ~ ~ ~
0 ~ ~ ~
~ ~ ~
~ ~ ~
~ 0 ~
I~0
~ ~
~ ~
0 ~ 4 ~ ~
~ ~ ~ ~
~
~
0
I ~ ~
~ ~ ~
~ 0
~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~
0 ~ ~ ~ ~ ~ 0 ~ ~ ~ 0 ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ I~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
'LD ~ ~ ~ II ~
~ ~
~ ~
h ~ ~ ~
I ~
~
~
~
~ ~ 0 ~ 4 ~ ~ 4 ~ ~
N ~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~
~
~
I
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ 0
~ ~
~ ~ ~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
I
~
~ ~ ~
I
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I
~ ~
~ ~ ~
~ ~ ~
~
~
~ ~
~ ~
II~ h
~ ~ ~
0 ~ 4
~ ~ ~ ~
0 ~ ~
~
~
~
~
~
0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ 4 ~ 0 ~ ~ ~ ~ ~ ~ 0 ~ ~ ~
44 0 ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4 ~ ~ ~ ~ ~
~ ~ ~
I 0 ~ ~ ~
~ ~ ~ ~
~
~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ 4 4 ~
~ I ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~
~
I
I
~ ~ ~ ~ ~ ~ ~
LJ
m N J
4I
m~NI4asrgr
LFI
m rrSI
K K R
~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ 0 ~
~ ~ ~ 0 ~ ~ ~ ~ ~ I ~ ~ I ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ 0 ~ ~ ~ ~
I~~
~
~ ~
~
~ ~
4 ~ 0 ~ S
~ 0
~ a
~
0 ~ ~ ~ ~ 0 ~ ~ ~
~ ~
~
~ ~
~ ~ 4
~
~
~ ~
~ ~
~ 0
~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ 0 0
~ ~ ~ Il ~ ~ ~ ~ ~ a ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ D ~ P ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 ~ ~ ~ ~ ~ 0 ~ 4 ~ ~ ~ ~ ~ ~ 0 0 ~ ~ ~ ~ ~ ~ ~ I~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~
~ 4
~ ~ ~
0
0
~ 4
0 4 ~ 0
~
~ ~
0
~ ~
~
I ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ I ~ ~ ~ ~
~ ~ 0
~ ~ ~
~ ~ ~
I ~ ~
~ ~
I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ I ~
~ ~
~ ~
~ ~
~ ~ ~ ~
0 0 I ~
~ ~
4 0
~ 4 ~ ~ 0 0
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~
I ~ 0
~ ~
~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ 0 0 ~ ~ ~ 4 ~
~ ~ ~
~ ~ ~
~
~
~ ~
~ ~
~ ~ 0
~ ~
~ ~
0 ~ ~
~ ~ ~
~ ~ ~
~ ~
~
~ ~ ~
~ ~ 0 ~ ~ ~
~ ~ ~
0
4
~ ~
~ ~ ~ ~
~
~ ~ ~ ~
~ ~
I ~ ~ ~ ~
~ ~ 0 ~
~ ~ ~ ~
~ ~ ~ ~
~
~ ~ ~
~ ~
0 ~
~ ~ ~
I II
~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ S ~ ~ ~ ~ ~ ~ 0 ~
~ ~
~ ~
~
0
~
~
~ ~
~ ~ 0 ~
0 ~ P ~ a
4 ~
0 ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ 0 ~ ~ ~
~ ~ ~ ~ 0 ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~
I
~ ~ ~ ~
0 ~ ~ ~
~ ~ ~
~ ~ ~
~ ~ 0 ~ ~
~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 0 ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~
I 0
~
~ ~ ~
~ ~
~
~
I
~ ~ 0 ~ ~ ~ ~ ~ 0 ~
I ~ ~ ~ 0 ~ ~ ~ ~ ~ P 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ I ~ I ~~~ ~h~ ~ ~ 0 0 4 ~ ~
~ ~
~
~ ~ ~ ~
~ 4
~
~
4
~ ~ ~
~ ~
~ ~
4 ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
0
~ ~
~ ~ ~ ~
~ ~ ~
~ ~
0 ~I ~ ~ ~ ~ ~
~ ~
I ~ ~
~ ~ ~ ~
~ 0
0
~ ~ ~ 0 ~ ~ ~
~ 0
~
I ~ ~ ~ 0 0 ~
~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ 0 ~ ~ ~ ~ ~ ~ ~
~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 0 ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~
~ ~
~
0
~ ~ 0
~ ~ ~
~
0 ~ ~
h ~ ~
a
0
~ 0 ~
0 ~ 0 ~ ~
0 ~ 0 ~ ~ ~ ~
I
~ ~ ~
~
~ ~ 0 a ~ a
~ ~ ~ I ~ ~
~ ~ ~ 0
~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ P
~ 0 ~
~
0
~ ~ ~
~ ~ ~
~
~
~ ~ ~
0 ~ ~ ~
0 0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ P 0
I ~ h ~ ~
~ ~ ~ ~ ~
~ ~ ~
~ 0 ~
~ 0
~ ~ ~ ~ ~ ~ 0 ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~
4
0
~ I 0
I D ~ ~ ~ I ~ I 0 ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~
I
~ ~
4
~
~ ~ ~
~ ~ ~ ~ ~ ~ I ~0 0
~
~ ~ 0 0 ~
~ ~ ~ ~ ~ ~
~ ~
~ I ~ 0 0
~ ~
~ ~
~ ~ ~
~ 0 0 ~ ~
~ ~
0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 0 ~ ~
~ ~ 0
~ ~ ~ h
~ 0 ~ ~ ~
~ ~ ~ 0 ~
~
~
~
4
~ ~ ~ ~ ~ ~
~ ~
Il
~ ~
0 ~ ~ ~
I ~ ~
~ ~
0 0
~
~ 0 ~
~ I ~~I ~
~
~ ~ ~
~ ~ ~ ~ 0 ~ 0 ~ ~ ~ ~ ~ ~ I ~ ~ ~ 0 0 ~ ~
~ ~ ~ ~
~
4
~
~ ~ 4 ~
~ 0 ~
4 ~ 0
~ 0 ~ ~ ~ ~ ~
I I
~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~ ~ ~ ~ S ~
~ 0 ~ ~ ~ ~ 0 ~ ~
~ ~ ~ ~ 4 ~ 4 ~ ~ 0 ~ ~
I ~0 ~~ ~~ 0~ ~~ ~
~ ~ ~
I I I
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
I I ~ ~
0 0
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ I 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 4 ~ ~
I I
~ ~ I 0 0 0 ~ ~ ~ ~ ~ ~ ~ ~ 5l ~ ~ ~ N I ~ ~ ~ N ~
I ~ ~
~ ~ ~ 4
~ 0 ~ ~
~ ~
~
~ ~ ~ ~
~
I ~ II
~ ~
~ ~
~
I P
~
4 ~ I
~ ~
~ I ~
IQ ~ ~ ~ ~
~ ~ ~ ~
I
~ ~
~ N ~ ~ ~
~ 0 ~ m
~ I I I
~ ~
~ ~
4 ~
4
~ ~
~ ~ ~ ~ ~
4 ~
4 ~ ~
~ ~ ~
0
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ 0
~ ~
~ ~
N ~ ~ ~ ~
~ ~ ~ ~
N I~ ~~ I~ ~~ ~
~
I
~ 0
~ ~
~
0
~
~
~
~
~
~ I ~ ~
~
4 ~
~ ~
~ ~ I
~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 I
~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ I ~~ ~~ I~ ~
~
~ ~ 4 ~ ~ 0 0 ~ 0 ~ ~ 0 ~ ~ ~ ~ ~
~ ~
~ 4
~
0 ~
~
~
~ ~
~ ~ 0 ~
~ ~
~ ~
I
~ 0 ~
~ ~ ~
I ~ ~ ~ ~ ~I~ ~ ~
~
~ I ~
~
~ ~ ~ ~ ~ ~ ~ I ~
~
0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~
~
~ 4 I 0 ~I~
~ ~ ~ ~ ~ ~
~ ~ ~
0 ~ ~ ~
~ ~
~
I ~ ~ ~
~ ~ ~I ~ ~
0 ~ ~ ~
~ ~
~ ~ IQ
~
~ ~
I
~ ~ 4 ~ I~ ~ ~ ~
~ I~ I~~
~
~
4 0 ~ ~ ~
~ 0 ~ ~
IQ ~ ~ 4 IQ 4 ~ ~ 0 I ~ ~ ~ ~
~
~ ~ ~ ~ ~
4
~ ~
~ ~ ~ ~ ~ ~ ~ ~
IQ ~ ~ ~ ~ ~ ~ ~
~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I I
~ ~ I ~ ~ ~
I I ~ ~ ~ 4 ~ ~ ~ ~ ~ ~
5I ~ ~
~ ~
~
~
~
~
4 ~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~ 0 ~
~
~
~ ~
~ ~ ~ ~
~ ~
~
~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~
I ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
5l ~
~
~
~
~ ~ Cl ~ ~
~
~ 4 ~ ~
~
~ ~
~ ~ ~ ~ ~ ~ ~
I ~
~
~
~ ~
I ~ ~
~ ~
~ ~ I ~
~ ~ ~
~ ~
I
~ ~
I~ 5l
~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ I ~ ~
~ 0 ~ ~
~ ~ ~ ~
I0 ~ I ~ ~ ~ ~ ~
~
~
~
~
~
~ ~
~ ~ I
~ ~
~ ~
~ ~ 4
~ ~ ~ ~
~ ~
~
~ I 0
~ ~
~ ~ ~ ~
~ ~ ~
~
~ ~ ~ ~
I ~ IQ 4 ~ ~ ~ ~ ~
I~ ~
~ ~
~ 44
~ ~ ~ 4 ~ 44
~ ~ ~ 0 ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
IQ ~
~
~
~
IQ ~
~
~ ~ ~ ~
~ ~ I ~ 4 4
4 I ~ 0
~ 4
~ I I
0 ~ ~ ~
~ ~ 4
~ ~ ~
~
~ ~
~
4
I ~ ~ ~ ~ 0 ~ ~ ~ ~
LJ
al Fr m 'lr lg'I
LJ
m NA 4 ~'Imr mls
Ih l' Pl 4 m O II -
rr IF 4 ar m r m O
N N N rF N N N N N N SI
LJ
N
LJ
m Nmaalgr
LJ
JD g N IF J
LJ
m r„rF ~
R lL R IX K
~ ~ ~ 0 ~
I I P
I ~ 4 ~ ~ ~ ~ ~ ~ 0 ~ ~ ~
~
~ I ~ ~
0
0 4 ~ ~ 4 ~ 4
~ ~ ~ ~
0
~ ~ P 0 ~
4 ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
0 ~ ~
I ~ ~ ~
~ ~ ~
P
~ 0
~
~
~ ~ 0 0 ~ 0 ~ ~ ~ ~
~ ~ ~
~
~
~
~ ~
~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ I~ ~ ~ ~ ~ 0
~ ~ ~ 0 ~ ~ ~ ~ 4 ~ ~ 4 ~ ~ ~ ~ ~ ~ 0
~
~
~ ~ ~ ~
~ ~ ~ 0 ~
~ ~ ~ ~
~ ~
0 0 ~
~ ~ ~
0 ~
~ ~ ~
0 ~ ~ ~
~ ~ ~ ~ ~ ~
4 ~ I ~ ~ ~ ~ ~
~ 4
~ ~
~ ~ ~
~ ~ ~ ~
~ ~
~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ 0 ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
III
~ ~ ~ ~ ~ ~
~ 0 4 ~ ~ 4 ~ ~ ~ ~ 0 ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~
~
~
~ ~
~ ~ ~
~ ~ ~ ~
~ I ~ 4 0
~ ~ ~ ~
I
~
~ 0 ~
~ ~ ~ ~
~ 0 0
~ ~ ~ ~
~ ~ ~
~ ~ P
~ ~
~ ~
~ ~
~
~ ~
~
~
~
~
~
0
~
~ ~
~ ~ ~ ~
~ 0
~ ~ ~
~ 4
I ~
0 ~ 0
~ 0
~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ 0 ~ ~ 0 ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
I~ I ~ ~ ~ ~
I I
~
~ ~
4
~ 0
~ ~~
~ ~
~ ~
~ ~ ~
~ I ~ ~ 0 ~ ~ ~ ~ ~
~ ~ 4 ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
~ ~
4 0
4 ~ ~ ~ ~ ~
~ I ~ ~
~ ~
~ ~ ~
~ ~ ~ ~ ~ ~
~
~ ~ ~
~ ~
I 0 ~
~ ~
0 4 ~ ~ ~ ~ ~ ~
I ~
4 ~ I ~
~ ~
~ ~ ~
0
~ ~ ~ ~
0 ~ 4 ~
~ ~
0
I
~ ~
0
~
4
~ 4
~ ~
~ ~
0 ~ ~ ~ ~ P ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 0 ~ ~ I ~ ~ ~ ~ 4 ~ ~ ~ ~
~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 0
~ I ~
~
~
~
~
~
~
~
~ ~ ~
~ ~ ~
~
~ ~ ~
~ ~ ~
I I 0
~ ~
~ ~ ~ ~ ~ ~
~ P ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ I
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ a ~ ~
~ 0 4 ~ ~ ~ 0 ~ ~
~ ~ I ~ ~ ~
I
~
0 ~
~ ~ ~ ~
0 ~ ~ ~
0
0 ~ 0
0 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ 4 4 ~ ~
4
0
~ ~ ~ ~
~ ~ ~
~ ~
~ ~
4 ~
~ I
4
~ ~
I ~ ~
0 ~ ~ ~ ~ ~ ~ ~ 4
P I ~ ~
I ~ ~ ~ ~ ~ ~
I ~ ~ ~ ~ 4
I ~ ~ ~ 0 ~ ~ ~ ~ ~ ~
~ ~
~ 5l ~ ~ ~
~ 0
~ ~ ~ ~ ~ ~ 4 ~
~ ~
~ ~ 0 ~
I ~ ~ ~
~
~ ~ IA ~ P ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
4 ~ 0 0
I ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~
~
0
0 0 ~
I
~ ~
~ ~ 4 ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ P ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~
~ ~ ~ ~
II
~ ~ 4 ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ I
~ ~ 4 ~ ~ ~ ~ 4 I ~ ~ ~ ~ ~ 0 5l ~
IQ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ IQ 5l
P
I
I ~ 4 ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ 5l
~ ~ 4 ~ ~ ~ ~ ~
~
~
~
~ ~ ~ ~ ~ 4 ~ ~ ~
~ ~ ~ ~
~
~ ~
~
5l ~ ~ IQ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~
4 ~
~ ~
~ ~ ~ ~ ~
~
~ ~ ~
~
5l ~
IQ ~
~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~
k
F
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ 5l
~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I 44
OO
8
1
2
3
4 4 ~
5 ~
5 ~
6 6
7 ~ 7 ~
8 e
9 9
18
ll 11
12
12
13 13
14 14
15 15
16 16
17 17
1e 18
19 19
28 28
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
38 38
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
48 48
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
58 58
51 51
52 52
53 53
54 54
55 55
56 56
57 57
58 58
59 59
68 68
61 61
62 62
63 63
64 64
65
66 66
67 67
68 68
69 69
78 78
71 71
72 72
73 73
74 74
75 75
76 76
77 77
7e 7e
79 79
88 e8
FIG. 9. Time evolution of a simple initial state according to the modulo-two rule 90, on a line of sites satisfying (a) periodic boun-
dary conditions (so that first and last sites are identified, and the sites are effectively arranged on a circle), and (b) null boundary con-
ditions (so that sites not shown are assumed always to have value 0). Changes in boundary conditions apparently have no significant
qualitative effect.
"
Other simple rules serve as filters for s p ecific initial f'
states containing a ini tee nu number of sites with value
I
ina densities proportional to the ini- may be obtained by additive superpositio n.. If the initia
~ ~ ~
ing final
~ ~
ieldin
~
sequences, yie
' '
1 d it of the sequences to be selecte . or ru e f
configuration is one wwhich would be reached by evolution
final density is equal to the initial density ensit oof 101 se- irn ste s, then the result-
from a single site after, say, v. p time p,
quences, so that p =pp (1 — p ). For rule 36, p„ is deter- ing density is given b y Eq.. (3.2) with the replacement
mined by the density of initial 00100 and. . .
— 0
nyave
1 very small fraction of initial con igu-
sequences and is approximately for pp ——, .„ rations may be treated in this way, since evolutio~ from a
Exact results for the behavior o.f p, wi with the modulo- single site generates only one o of tthee 2" possi
ossible configura-
two rule 90 may b e derived
eriv using the additive superposi- hi.
tions in w ic h the maximum separation etween nonzero
etw
tion property discussed in Sec. Se . II. sites is k. For sma 11 or highly regular initial con fiigura- ura-
Consider first the number of sites N, ith 1 b- 1o- tions, results aria ogous too (3.2) may nevertheless be de-
' '
d by evo/ution according to ru lee 90 from an initial ed. Statistical results for evolution ro rom disordered d in-
'
state containing a single sitee wi with value 1, as illustrated in itial states may also be derived. Eq uation (3.2) implies
Fig. 3 . G eometrical considerations b a sed on Fig. 'g 5 yie that after exactly 7. = —2 time ssteep, s an initial state contain-
the result 6 le nonzero site evolves to a co nfi'g uration wit
gl(7-) onl y two
on nonzero sites. At this point, t e vvalue of a p ar-
wo no
N,()) = 2 (3.2) 1 r site at position n is simply the sum mod rnodulo two of
the initial values of sites at positions n — w and n+r. If
~ ~
currences off t h e d'igiit 1 in the binary representation n o we start from a disordered initial configuration, the densi-
integer r, as d ef'ineed above
a and is illustrated in ig.
Equation (3..2)) may b e derived as follows. Considerer thee
of tthee
ty at such time steps is thus given by p, =
=2p p(1 —pp).).
In general, the value of a site at time step r is a sum much flatter than that for rule 90 (illustrated in Fig. 12).
modulo two of the initial values of N, =2 sites, An exact result may be obtained, but is more complicated
which each have value I with probability po. If each of a than in the case of rule 90. The geometrical construction
set of k sites has value 1 with probability p, then the prob-
"'
of Fig. 6 shows that for rule 150, N, is a product of fac-
ability that the sum of the values at the sites will be odd j
tors X(j) associated with each sequence of ones (delimit-
ed by zeroes) in the binary representation of r. The ex-
(equal to 1 modulo two) is
j
pression p( ) is given by the recurrence relation
p'(1 —p)" ' = —, [1 —(1 —2p)"] . j) j
X( = (2j+ 1)X( —1) where the upper (lower) sign is tak-
i odd en for j odd (even), and X(1)=3 [so that X(2)=5,
"'
X(3)=11 and so on]. [N, thus measures "sequence
Thus the density of sites with value 1 obtained by evolu-
tion for r time steps from an initial state with density po
correlations" in r ]T.
he density is then given in analogy
according to cellular automaton rule 90 is given by p, = —, [1 —(1 —2po} ].
with Eq. (3.3) by ' N('
ceptional time steps r =2", the p, for rule 150 tends to be a sequence of (perhaps small} "domains, in each of
which either all even-numbered sites or all odd-numbered
sites have value zero. These domains are then separated
by "domain walls" or "kinks.
" The kinks move in the
cellular automaton evolution and may annihilate in pairs.
The motion of the kinks is determined by the initial con-
figuration; with a disordered initia1 configuration, the
kinks initially follow approximately a random walk, so
O. 75— rule l82
that their mean displacement increases with time accord-
ing to (x ) =t (Grassberger, 1982), and the paths of the
kinks are fractal curves. This implies that the average
T kink density decreases through annihilation as if by dif-
0.50 fusion processes according to the formula (pk;„k )
—(4mt) '~ (Gras. sberger, 1982). Thus after a sufficiently
long time all kinks (at least from any finite initial config-
uration) must annihilate, leaving a configuration whose
alternate sites evolve according to the additive cellular au-
0.25 tomaton rule 90. Each point on the "front" formed by
i
structure appears with rule 22, and the approach fails. that the master equation (3.4) yields equilibrium densities
Simulations yield a numerical estimate p =0.35+0.02 within 10— 20%%uo of the exact values. The discrepancies
for evolution from disordered configurations with any are a reflection of the violation of the Markovian approxi-
nonzero po. mation required to derive Eq. (3.4) and thus of the pres-
Figure 12 shows the behavior of p, for the complex ence of correlations induced by cellular automaton evolu-
nonadditive cellular automata 18 and 182 with p0=0. 2, tion.
and suggests that the final constant values p =0.25 and In the discussion above, a definite value for the density
p =0.75 are approached roughly exponentially with p, at each time step was found by averaging over all sites
time. of an infinite cellular automaton. If instead the density is
One may compare exact results for limiting densities of estimated by averaging over blocks containing a finite
cellular automata with approximations obtained from a number of sites b, a distribution of density values is ob-
statistical approach (akin to "mean-field theory" ). As dis- tained. In a disordered state, the central limit theorem en-
cussed above, cellular automaton evolution generates sures that for large b, these density estimates follow a
correlations between values at different sites. Neverthe- Gaussian distribution with standard deviation =1/~b
less, as a simple approximation, one may ignore these Evolution according to any of the complex cellular au-
correlations, and pararnetrize all configurations by their tomaton rules appears accurately to maintain this Gauss-
average density p, or, equivalently, by the probabilities p ian distribution, while shifting its mean as illustrated in
and q =1 — p, assumed independent, for each site to have Fig. 12. Density in cellular automaton configurations
value 1 and 0, respectively. With this approximation, the thus obeys the "law of large numbers. " Instead of taking
time evolution of the density is given by a master equa- many blocks of sites at a single time step, one might esti-
tion mate the density at "equilibriuin" by averaging results for
a single block over many time steps. For nonadditive
5p = I (0 1) —I (1 0), complex cellular automaton rules, it appears that these
5~
two procedures yield the same limiting results. However,
I (0~1) = P (00110011AR), (3.4) the large fluctuations in average density visible in Fig. 12
at particular time steps for additive rules (90 and 150)
r(1 0) = P. (1 lool loon, -R), would be lost in a time average.
P = Ip'p'q p'q pq'p'q pq'pq'q'I . Cellular automaton evolution is supposed to generate
correlations between values at different sites. The very
The term I (0~1) represents the average fraction of sites simplest measure of these correlations is the two-point
whose values change from 0 to 1 in each time step, and correlation function C' '(r)=(S(m)S(m+r)) —(S(m))
I (1~0) the fraction changing from 1 to 0. R is the )& (S(m + r ) ), where the average is taken over all possible
binary specification of a cellular automaton rule, and the positions m in the cellular automaton at a fixed time, and
binary number with which it is "masked" (digitwise con- S(k) takes on values —1 and +1 when the site at posi-
junction) selects local rules for three-site neighborhoods tion k has values 0 and 1, respectively. A disordered con-
with appropriate values at the center site. P is the vector figuration involves no correlations between values at dif-
of probabilities for the possible three-site neighborhoods,
assuming each site independently to have value 1 with
ferent sites and thus gives C' '(r ) =0 for r 0
[C' '(0)=1 —(2p —1) ]. With the single-site initial state
)
probability p=p, and to have value 0 with probability of Fig. 3, evolution of complex cellular automata yields
q=1 — p=1 —p. The dot indicates that each element of configurations with definite periodicities. These periodi-
this vector is to be multiplied by the corresponding digit cities give rise to peaks in C' '(r). At time step r, the
of the binary sequence, and the results are to be added to- largest peaks occur when r =2 and the digit correspond-
gether. The equilibrium density p is achieved when ing to 2 appears in the binary decomposition of ~; small-
P 0
er peaks occur when r =2 +2,
kI k2
and so on. For the ad-
5~ ditive cellular automaton rules 90 and 150, a convolution
of this result with the correlation function for any initial
This condition yields a polynomial equation for p and state gives the form of C' '(r) after evolution for r time
thus p for each of the legal cellular automaton rules. steps. With these rules, the correlation function obtained
For rule 90, the equation is pq — p =p— 2p by evolution from a disordered initial configuration thus
= p(1 —2p) = 0, which has solutions p =0 (null state for always remains zero. For nonadditive rules, nonzero
all time) and p = —,. Rule 18 yields the equation short-range corrdations may neverthdess be generated
pq — 2p q — p = p(1 — 4p+2p ) = 0, which has the from disordered initial configurations. The form of
solutions p=0 and p=1 —1/t/2=0. 293, together with C' '(r } for rule 18 at large times is shown in Fig. 13, and
the irrelevant solution p= 1+ 1/t/2) 1. Rule 182 yields is seen to fa11 roughly exponentially with a correlation
2pq pq = p(2 —3p}(1— —p) = 0, giving p=0, 1, —, . length -2. The existence of a nonzero correlation length
For rules 90 and 18, these approximate results are close to in this case is our first indication of the generation of or-
the exact results 0.5 and 0.25. For rule 182, there is a sig- der by cellular automaton evolution.
nificant discrepancy from the exact value 0.75. Neverthe- Figures 3 and 8 show that the evolution of complex cel-
less, for all complex cellular automaton rules, it appears lular automata generates complicated patterns with a dis-
IO 20
FIG. 13. Two-point correlation function C'-"(r) for configura- For small k, the triangle density in this case does not behave
tions generated at large times by evolution according to cellular as a pure power of 2 . Whereas the solution to any one-term re-
automaton rule 18 from any disordered initial configuration. currence relation, of the type found for cellular automaton rule
C"'(r) is defined as (S(m)S(m +r})—(S(m)) (S(m +r}), 90, is a pure power, the solution to a p-term recurrence relation
where the average is taken over all sites rn of the cellular au- is in general a sum of p powers, with each exponent given by a
tomaton, and S(k) = +1 when site k has values 1 and 0, respec- root of the characteristic polynomial equation. In the high-order
tively. No correlations are present in a disordered configura- limit, the solutions are dominated by the term with the highest
tion, so that C' '(r)=-0 for r &0. Evolution according to certain exponent (corresponding to the largest root of the equation).
complex cellular automaton rules, such as 18, yield nonzero but
exponentially damped correlations.
Complex roots yield oscillatory
= —f(k —1)+f(k —2); f(0)=0, f(1)=1].
behavior [as in f (k )
mension D=log23 — 3
1 =log2( —, )=0. 59. The second form For nonadditive rules A, ——, , while for the additive rules
may be deduced directly from the geometrical construc- A, -2. The same results are obtained at large times regard-
tion of Fig. 5. For rule 150, the configurations have frac- less of the density of the initial state. Thus the spectrum
tal dimension D =log2y. of triangles generated by complex cellular automaton evo-
Figure 14 shows patterns generated by evolution with a lution is universal, independent both of the details of the
selection of complex cellular automaton rules from initial initial state, and of the precise cellular automaton rule
states containing a few sites with value 1, extending over Used.
a region of size no. Comparison with Fig. 3 demonstrates The behavior (3.8) of the triangle density with disor-
that in most cases the patterns obtained even after many dered initial states is to be contrasted with that of (3.5) for
time steps differ from those generated with a single initial simple initial states. The precise form of an initial state
site. A few exceptional initial configurations (such as the of finite extent no affects the pattern generated only at
one used for the first rule 90 example in Fig. 14) coincide length scales &no. at larger length scales the pattern
with configurations reached by evolution from a single in- takes on a universal self-similar character. A disordered
itial site and therefore yield a similar pattern, appropriate- initial state of infinite extent affects the pattern generated
ly shifted in time. In the general case, Fig. 14 suggests at all length scales and for all times. Triangles of all sizes
that the form of the initial state determines the number of are nevertheless obtained, so that structure is generated on
triangles with size n (no, but does not affect the density all scales, as suggested by Fig. 15. However, the pattern
of triangles with n »no As a. simple example consider is not self-similar, but depends on the absolute scale de-
the modulo-two rule 90, whose additive superposition fined by the spacing between sites.
property implies that the final pattern obtained from an Disordered configurations are defined to involve no sta-
arbitrary initial state is simply a superposition of the pat- tistical correlations between values at different sites.
terns which would be generated from each of the nonzero They thus correspond to a discrete form of white noise
initial sites in isolation. These latter patterns were shown and yield a flat spatial frequency spectrum. One may also
in Fig. 5, and involve the generation of a triangle of size consider "pseudodisordered" configurations in which the
2 at time step 2 . The superposition of such patterns value of each individual site is chosen randomly, but ac-
yields at time step 2 a triangle of size at least 2" — 2no. cording to a distribution which yields statistical correla-
This conclusion apparently holds also for nonadditive tions between different sites, and a nontrivial spatial
complex cellular automata, so that, in general, for Fourier spectrum. For example, a Brownian configura-
n »no, the density of triangles follows the form (3.5), as tion (with spatial frequency spectrum I/k ) is obtained by
for a single site initial state. The patterns thus exhibit assigning a value to each site in succession, with a certain
self-similarity for features large compared to the intrinsic probability for the value to differ from one site to the
scale defined by the "size" of the initial state. One there- next (as in a random walk). The patterns generated by
fore concludes that patterns which "grow" from any sim- cellular automaton from such initial configurations may
ple initial state according to any of the "complex" cellular differ from those obtained with disordered (white noise)
automaton rules (except 150) share the universal feature initial configurations. Complex nonadditive cellular auto-
of self similarity, characterized by a fractal dimension mata evolving from a Brownian initial state yield patterns
log&3. On this basis, one may then conjecture that given whose triangle density T(n ) decreases less rapidly at large
suitable geometry (perhaps in more than one dimension, n than for disordered initial configurations: the "long-
and possibly with more than three sites in a neighbor- range order" of the initial state leads to the generation of
hood}, many of the wide variety of systems found to ex- longer-range fluctuations. In the extreme limit of a
hibit self-similar structure (Mandelbrot, 1977, 1982) at- homogeneous initial state (such as . . . 11111.. . or
tain this structure through local processes which follow . . . 10101. . . ), cellular automaton evolution preserves the
cellular automaton rules. homogeneity, and no finite structures are generated.
Having considered the case of simple initial configura- The appearance of triangles over a series of time steps
tions, we now turn to the case of evolution from disor- in the evolution of complex cellular automata from disor-
dered initial configurations, illustrated in Fig. 8. Figure dered initial states reflects the generation of long se-
15 shows the first 300 time steps in the evolution of cellu- quences of correlated sites in individual cellular automa-
lar automaton 126, starting from a disordered initial state ton configurations. This effect is measured by the "se-
with density p=0. 5. Triangles of all sizes appear to be quence density" Q~;~(n), defmed as the density of se-
generated (the largest appearing in the figure has n =27). quences of exactly n adjacent sites with the same value i
Figure 16 shows the density of triangles T(n ) obtained at (bordered by sites with a different value). Thus, for ex-
large times by evolution according to rule 126 and all of ample, Qio~(4) gives the density of 100001 sequences.
the other complex cellular automaton rules. The figure QIO~(n ) clearly satisfies the suin rule
reveals the remarkable fact that for large n, all nonaddi-
tive rules yield the same T(n), distinct from that for the nQ, o~(n} = 1 — p.
additive rules (90 and 150). All the results are well fit by n=1
the form In a disordered configuration with density p = 1 — q,
Q, o~(n }-p q" for large n Any sequence l.onger than two
T(n ) — A, (3.7) sites in a complex cellular automaton must yield a trian-
a a
U
g
~
4 4I tf
~ p
t
t~ t
4' ~
~
I g5
I
4 a ~ ~ 4 t
t
~
U ~ Ite
g
4
k 1
4 1
I a ~ e
P 4
I ke t Pt e t cd
2
4 1
t It~ t
4 4 ~ t c5
4 4
k
1
P
a 1
It I~ t~ ~ ~ t I~ ~ ~
4 a 4 4 1 I I~ Ia ~ e4 1 ~ 4 t ~ ~ e
e
t I I it
4 t t ~
I I I ~ t4 1P t ~ 44 tt
I bo . ~
I 4 4
I t 4 t k1 a~
~'
4 I I t ~ P 4
I1 I4 I 4
~ 4 t t
4 4 t f cA
1
k
it
4
If
if
4
tt
~ I
t a t ke t t 1 e t 1I e1 r .Q
I 4 4
k
4
t I I I ~ t I t t t e rt ~ qd ch
4 P I Q v
k
4 4 I4 I 4
I I
4
lf
k
I 4 t t 4 I
1 e 4'
bo
a$
k k
4
4 k 4 I I t1 t 2O
4
4
k I t 4
1
1 I
I' t I4
1 ~
t 4 1 tt Pt 4 Q~~ O
4 1 I I I t 4
I a
t k t P 4 I a t 4 e
I t 4
1 e
~ f
r
ff
a
O
k
4 k 4 P e
4 k If 1 te 1 P ~
4 1 4'
4 ~
t 4 4 ~
t
4 a
4
tt
t t t t ~ ~
4
1 4
4 k I4 at ~ a
t
4 a
4
~
aS
4
4 4 I
t ~
e
cd
~ ~ g N
cn c5
1
a cA
O
o C
V ~
c5 CO
~
k
4 4 t C
t 4
4 e I a
CA
I t t 1 O
e
a
4 4 1 t
k
k k t 1 k
~ 4 4 k t 1 e
I
4 O
I
k
~ t 1
1 ~
a I 4
k
I Q—
4
k 55 X
k
I
k
4 4 t 4
If
I k I
t t I m~cr E~ aQ
4
a 1 t 4 4 II ~
I I 4
I ~ t I IIt 4 q5
k k k t I
P
t ~
4
k
4
4
4
1 t
t4
t
4
o p
I k 4 4
1 1 I O
tt
4 k
k ~
t1 4 I 4 4 ~ I ~ t I k 4
~
k
k
I
4
4
k
k
I
~ I
4 4
e
~
4
I
I
~t
4
I t~ ItP
4
t ~
I I I
4 k
1
I I
P
I
I
I ~
4 ~ -
bQ
a
I t It
1 k 4 it
k 4
1 4
4 4 I t I
k I k
k 4 4 I ~
I I k 4 I4 a a 4
4
t a a
k
Ik 4 k
k
k
t
k 4 t ~ P cn
P ~
Ie k 4 Q
I ~ 4
4 4
k I
I a
O
k
k 4
4
4 4 o
k
k e I bo a5 Q
t
1 C
&u OW
o
P
2w~
4
~ ~ C
4
4 4
4 4
C
4 ~ k ~ ~
4 cn
4
~ 4
a 1 e ft
4 4
4 ~ 4
t ~
t
k
k
1 Q
e ijl
k e 4
Q
e
e 1
e 1 k 4 1 1
O Q
4
4 4
4
'
~ 1
e 4
4
1
P Q~Q~.
Q +a
e
~ t
p a
~ It
4
~
P E ~ &U
t
4 1 e ~ e t * ~ ~ t
4 e
e
4 1 It ~ 1
4 k
t e 1
4
4 4 I 1 ~ ~ "U
4 e p
~ ~ I cf
~ 1
t t 4
e
4 t t
4
1 t
4 ~
e
t
Cls ~C ~ gJ
4 4 4 e
a 1 4'
C4
4 Cd
k
If
4
p
4 4
4= B~ c5
(Q
A
Q
O. I
O. OI—
IO
T(n)
I
0-4
0 IO 20 30 40
7 =.
I
~ ~ IS ~ ~ 0 0 ~ ~0 ~ 1000 ~ ~ I 1 ~ II 01 ~ ~ ~00~ I
)
8 I0 I NI IO ~I ~~~ atl ~ 010 0~
9 t4 0~ I 00 N et0 ~ Ite ~ ~ I 1~ ~ 0 NI a II~
)0 ls ~ es I ~ 0000 ~ ls ~ I~I ~~0 I 0000 I~ 1 0I NI
25 00 I I I ~ t 0 ~ I I I ts I 0 10
26 I ~ ~ II 400001010 ~ 00 ~ 00'aa I ~ ee 00$0 ~ 0 ~ ee ~
I INI I~1 ~ 00 I ~~~
~ 10 ~ ~ I~~ ' al NI I
28 8 lt IS I 04 04 ~ ~ 0000 100 ~ 4 ~ et 01 10
I
10 I ~ 0 ~ NI 0II
'3 ~ IO ~ 01 1 ~ 0 ~0~ ~~ I I ~ ~ I ~ 04 ~ ~ 4 ~ '
38 00 ~ I ~ Oa ~ 0e~~~0 I ~ I I ~ I ~ 1IS4 ~ I 01 ~ ~ I IS
i() 2
aaa 114 0 ~ 40 Ie 0101101 ~ 0 ~ I Nla II aa'aa
~ N ~ I 0 ~ 0~ Nl ~ I ~ 1~ 0 ~ ~ Nl I t 1 ls I l' 0 ~ ~ a ~ ~ Isa ~ 0 101 I ~ 101 ~ ~ ~
~ aaaaIN NI 001 ~ I ~ ~ aea IS ~ 0 ~ I 1~
~a ~ 00 ~ II ~ a ~ ~0 ~ a I~ \
~ ~
1011 ~
IS
3 NI S I
~ ~ 01 ~~ 0~ *~ ~0 ~ 101 I ~ Nl N
a'
tea aaeaea ~ $000 ~ 110 ala ~ ~~~ aa ~ 0 I I atl ~ I~ IS ~ NI ~ I 10 ~ ISI
NI ~~ ~ 10
6 e aaa 111 01 I 0 ~ ee ~a NII0 I ~ IS 4 ~ ~ ~I ~I
I ~~ etee ~~ I~ I~ IS ~ I 1I 010000 ~ I ~ ~ e
8 0~I~ ~ 0 ~~ I 0000 ~ I e 140 ~ 11 ~ $1 ~ ~ I ~ 0000 ~ IS I W N
9 e aa 00 04 ~ 10 ~ IIO a e e ~ e ee 00 I 4 ~ e I I~1 IS
t t
0 ea1000 ~ 00
40 ~ 11 I0
SINN'tl ~ ~ I eat
Itaa at 0 ~I~ ~ 0
~I~I I
I I1 010 ~ $0
1I 0 0 ~ I I
II I ~ I ~
~I NI IN
I ~ ~
I ~
' 1 ~ I ~ ~ ~ 10 0~1
N
00 010 ~ ~ I 01 ~ I ~ 11
sites wit h va ue 0 (delimited by sites with value lj in configura-
v lue 12 NI NI NI NI
13 ~ 0 ~ ~ 1 I ~ 01'0 ~ I e I 0 ~ 0 ~ ~ 000180 0 II I0 ~ ~
=, u,
~ ~0 IO IS IO
~ at ~ 1 $41 ~ sate 0 ~ 00 ~ 0 ~ I ~ 00 ~ I
tions generate d b y ~r steps in time evolution accorr ing
~N Nl
23
2 II
0$ 0$ ~ ~
e 88 SI$84 ~ $18 ~ OSIS SO
~ 4 ~ 80 04N
NNISS
10 ~ 00 ~
~ 41 ~ I ~ ~ 000 I
NII I
01 I ~
~ 0NI ~ I~
NI
I ~
with the same average total density ha". been subt rac ted. Th is 27 ~ ~ '0401 ~ 401 ~ ~ ~ ~ II 00 ~4 NI ~~ I ~ ~
28 I II II I0 010 ~ ~ 0 ~
f v. =
~ ~0~
=0 b y definition.
' ~I NI NI
I Ie
shown in tne n figure for ) ' '
or 7. 1 is a manifestation n o se
38
00~
00000
1~0 ~ ~
INI
1~ 0 1
4 ~ 04
at ~ aa ~ I
04
~I Nl ~ IS ~
Ss0 ~
~e aa aa I ~
e 0 I'00
I ~ Nl
~ aea
by comparison of Figs. 8 an and 10. For large r, an equ&librium 4 IS ~ ' ~ lS IS 14 ~ ~ NI 'S 10 IS ~ ~ ~ N NI N ~
e0 I I '0 I I N' ~ IIII I 0 ~ ~ ~IS000 ~ 1~ 0 ~ 0~ I1 N ~ ~ I I ~ ISSI ~ I
1 I ~ Iae tat ~ I~~I
state is reached, w h'ic h ex hibits 01 1 ~ ~ ~
I 1~ 0 0 ~ as a 0~ ~ 0 ~ 0
an excess of long sequences
IO III
i i nces an
and ea 000 I ~ I a ~ I 1 1 ate ~ ~ I 0
eaa ~ ee 01 I 0\
0'00 se ~ $0 ~ 0 aa os I
00 ~ 00 ~ 0 ~ I
I ~ $4 '0 0 ~ ~ 1~ ~ et ~ a ~ ~ ~ OISIN IS
Ia tSt000 ~ ~ 41 NI40 ~ ~ 00 Ia I ~ 00 ~ a
t
18 ~ O'I ~ I 00 0 e~0
e
00 ~ 00 ~ I
e
III I~
e~
00 ~
~I NI
(I —p )" an d
depend on total average dennsit y p for the con-
1 '3
20
1 ~ $0 0 ~ e a ~ ~ ~ ~
ae eee0100
~ ~ 14 ~ I ~ I ~
~ ~INIWSNI
II~II0
I~ II~ ~ ~
I 4 ~ ONIIS 0 ~ 00 ~ ~ ~ I
~ I4
4
I
~ 40 0 ~ ~ I~ ~
$4 01 I I I 4 00 0 I I
~ e 01
~ ~
Nllaala Ical 0 S
N
NI
' I
I
NI
NI Nl I ~I
I ~
11110~ 0 ~ II ~ 01 Ne ~ 10 ~ ~
figurations. T h e form
~ 04
rm (3..5) yields sequence correlatiotto 2
'&
~
tions
I
&
3 ~ I~ ~~ I ~ 4 II0 ~~ ~ I~ ~~ ~ 8 00 ~ I 1 111 ~ ~ I IS ' I
' d ~ ~ ~ I ~ It ~ 0 ~ 0 Ill 00 I ~ 0 0 4 ~ I~ ~
I Nl I ~ I ~ ~ 101 0 ~ 4$$
I I I ~ 10 ~ ~ Nle I I ~ ~ 81 I ~
wit h ih e sa me exponential behavior, ut with a ixe Sa 0
~ I~ 0 ~ 1I
~ 0 1~
~ ~ I 010etl ~ ~~ 0~II IetIII ~ 01 ~ 0$0 I I I ~ ~
Nl
II
11 ~ ~ 00&00 ~I~~~~
I 0~ 0 ~
I~ I
0 I ~ 01048 ~ $00
00 04 11
~I
~~ I 00
101
' 29 I ~~ I~ ~ ~
I ~I ~~
8 ~ ~ 880 ~ ~ ~ ~ 01 I
I NI W NI
viewed as corre-
t" 025 a I I
0
NI
~
~
1
I
00
~
0~~~
~ ~ 0
S ~
~ ~
~I
1~
~
~
~
I
~ ~
~
ea
0
NI
0
~ ~
~
I
~~ ~
0 ~I
'alla
ea ~0 11
I~ ~
0a
~ a
1110 10 ~ ~
1
~
~
~
~ ~0~
~ ~ ~
~
ltaa
1a
0 I~1
a
0
at I
~I
e
a
~
~I
aae
0
~ I
~ ~
NI
~
~
~~
I
~ ~
4
00 ~
~
~ 1 at
~ ~ 0
01 I ~ ~
0t
~
I ~ ~
~ 0~ ~ ~
0 ~ ~
1I
I
0
~ ~ I ~ ~
0 I~
einie deterministic
~ I ~
ing to definite
in e local rules. In mmodelling g 8 I1 ~
I~I1 0~ ~ ~ ~
~0
800
SNIIS
~ ~ ~~
I0 0 0
aal ~ ~ ~ I ~
ea ~ 00 ~ ~
~0
0 ~ ~ ~
I~
I 0
~I ~ ~~~ I I
~
~ ~
I eea ~ e I~ I0
ri eat, 14
t5
16
~ ~
~~
I~0~
I ~0I
~ ~
I~
~ 4 NI
~ 4 N ~
~ IIISWS
1~
0 ell
~ ~ ~
~
~
~
1~I
Ill I
~
0~0~~
00 ~ I
~ I
Nl
0
~~
I~~
0 ~0
~ ~ 001 I I
1970 Schulman and Seiden, 1978; Gach et aj. , t
i8
~ '0
104e ~
0 ~ NINI ~ I I ~
~~~
~~ ~
~
Nl
~a
I ~ ~ 11 I
0
Ieee ~
I
~ 0
I
80 00
~~
t9 ~ ~ ~~ ~~ ~~~ ~ ~ ~ ~ e ~~~ ~ 0 ~~
~ NI
0 ~
00
~ IS INE ~INI
~ 00
0
~ ~~
~
00$0 ~
I I4
~
~
00
~ 0 ~ OO
' ~ 0
~ ~~
000
1$ I I
~ ~ Nl
~ 04 ~
~
~0~ ~
~4~
4 ~~
~
0 I
0~
0~
NI
Nl ~~
0~
I Nl NI I~I0~ I I ~ NI ~ IO II ~ 1~
~ ~~0
~ 0~ ~ I
~
~~
F
4101 ~ I ~ $0 I I S S ~ 0~~ 0000 ~ 0 I 0~
(If an energy ts as-
I
I~I~I
000 00 0110 ~ ~ 01 ~ ~ I
si,
2 '3 ~~ ~ e ee~~ ~ 0~ ~~~ ~
II
sociated with the reversal of a site ~ g'ives the Boltzmann 38 ~~ I ~ ~~ ~ I I ~ Nl ~ ~I I ~ ~ ~ 00 ~ 00000 0I ~ I
~~ I I
Investigation of d ensities and correlation unctions indi- every time step. (a) is for ~ =0 (no "no~se }, (b) for K =
cates that the transition t o disorder is a continuous one, for v=0 2, and (d) or ~= =0.. 5.. Ass v increases, the structure
a"
and no phenomenon analogous too "phase transition" is
I ~ ~
behaves as H =r logg3 —1
=~ p 59. For nonadditive rules,
the difference between configurations obtained through
200— cellular automaton evolution no longer depends only on
the difference between the initial configurations. Figure
20(c) shows the difference between configurations ob-
tained by evolution according to the nonadditive cellular
automaton rule 126. The lack of symmetry in the pattern
is a reflection of the dependence on the values of multiple
iOO—
initial sites. Figure 20(b) shows the Hamming distance
corresponding to this difference. Apart from small fluc-
tuations, it is seen to increase linearly with ~, tending at
large r to the form H, =r. This Hamming distance is the
same as would be obtained by comparing sequences of 2r
F00 200 sites in two disordered configurations with density 0.5.
Thus a change in the value of a small number of initial
sites is amplified by the evolution of a nonadditive cellu-
lar automaton, and leads to configurations with a linearly
increasing number of essentially uncorrelated sites.
(Changes in single sites may sometimes be eradicated after
a single time step; this exceptional behavior occurs for
200- cellular automaton rule 18, but is always absent if more
than one adjacent site is reversed. ) A bundle of initial tra-
jectories therefore diverges with time into an exponential-
ly increasing volume.
H One may specify a statistical enseinble of states for a
finite cellular automaton by giving the probability for
i00—
each of the 2 possible configurations. In a collection of
many disordered states with density p= —, , each possible
cellular automaton configuration is asymptotically popu-
lated with equal probability. Such a collection of states
wi11 be termed an "equiprobable ensemble,
" and may be
I
0 ill
0
I ii, L i J, Ji J Ji / IIII
I024
may appear as initial conditions but may never be reached
as descendants of other configurations through cellular
automaton time evolution. ' Such configurations carry
zero weight in the ensemble obtained by cellular automa-
ton evolution. In the trivial case of cellular automaton
FIG. 21. Probabilities for each of the 1024 possible configura- rule 0, only the null state with all sites zero may be
tions in a finite (circular) cellular automaton with length N =10
reached by time evolution; all other configurations are un-
obtained by evolution according to rule 126 for ten time steps
from an initial ensemble containing each possible configuration
reachable. Rule 4 generates only those configurations in
with equal probability. On the horizontal axis, each configura- which no two adjacent sites have the same value. The
tion S is labeled by a ten-digit binary integer (marked in decimal fraction of the 2 possible configurations which satisfy
form) whose digits give the values of the corresponding sites. this criterion tends to zero as X tends to infinity, so that
The null configuration (with value zero at all sites) is labeled by in this limit, a vanishingly small fraction of the configu-
the integer 0, and occurs with the largest probability =0. 13 ~ rations are reached. Cellular automaton rule 204 is an
The inequality of the probabilities for initially equiprobable con- identity transformation, and is unique among cellular au-
figurations is a reflection for self-organization. tomaton rules in allowing all configurations to be reached.
(The rule is trivially reversible. ) Assuming periodic boun-
dary conditions, one finds that with N odd, the complex
ton sites. Then the equilibrium ensemble of cellular au- additive rule 90 generates only configurations in which an
tomaton configurations analogous to those of Fig. 22 cor- even number of sites have value one, and thus allows ex-
responds to a set of points on the real line. The unequal actly half of the 2 possible configurations to be reached.
1
probabilities for appearance of 0 and 1 digits, together For even N, —, of the possible configurations may be
with higher-order correlations, implies that the points reached. A finite fraction of all the configurations are
form a Cantor set (Farmer, 1982a, 1982b). The fractal thus reached in the limit N~ oo. For the complex nonad-
dimensionality of the Cantor set is given by the negative ditive rule 126, inspection of Fig. 8 shows that only con-
of the entropy discussed below, associated with the en- figurations in which nonzero sites appear in pairs may be
semble of cellular automaton configurations (and hence reached. Figure 23 shows the fraction of unreachable
real-number binary digit sequences) (Farmer, 1982a, configuration for this cellular automaton rule as a func-
1982b). For rule 126 the fractal dimension of the Cantor tion of N. The fraction tends steadily to one as N~ ao. A
set is then 0.5. complete characterization of the unreachable configura-
An important feature of the elementary cellular auto- tions for this case is given in Martin et al. (1983); these
mata considered here and in Sec. III is their "local ir- configurations are enumerated there, and their fraction is
reversibility. "
Cellular automaton rules may transform shown to behave as 1 — A, for large N, where A, =0.88 is
several different initial configurations into the same final determined as the root of a cubic equation. Similar
configuration. A particular configuration thus has unique behavior is found for other nonadditive rules.
descendants, but does not necessarily have unique ances- Irreversible behavior in cellular automata may be
tors (predecessors). Hence the trajectories traced out by analyzed by considering the behavior of their "entropy" 5
the time evolution of several cellular automaton configu- or "information content" — S. Entropy is defined as usu-
rations may coalesce, but may never split. A trivial ex- al as the logarithm (here taken to base two) of the average
ample is provided by cellular automaton rule 0, under
which all possible initial configurations evolve after one
time step to the unique null configuration. In a reversible
system, each state has a unique descendant and a unique The existence of unreachable or "garden-of-Eden" configu-
ancestor, so that trajectories representing time evolution rations in cellular automata is discussed in Moore (1962) and
of different states may never intersect or meet. Thus in a Aggarwal (1973), where criteria (equivalent to irreversibility) for
reversible system, the total number of possible configura- their occurrence are given.
~we 0N os I ~ ~ ao 0~ ~ «I ~ ~ OI ~ ~ H ~ ~ ~ NO So ~ 0 ~ ~~ 0 A ~ ~ 0 ~ ~ 0 ~ ~ ~ 0 Ol ~ ~ ~S ~ ~ H ~ ~ ~
as ~ ~ sa ~ ~ ~ so0 w ~ ~ 0 ~ ~
H ~~ ~ ~ ~ ~ aoo r ~ 0 ~ ~
Os IOI 0t ~ We ~ Oo ~ ~ so ~ ~ ~ NO se ~ 0~ ~
0 ~~H ~ ~ ~ NO H ~
~ ~~ osrooa svo N ~ Hor ~ ~~ ~ ~ ~ NH ~ eos oev oooo NIH »HH 0 ~~ H Iv o»INI No ~ oor ooe« ~~ How v oN NHI ~ os tools ~ IN Ho ~ Oo I V 0 N sV H» I ~ HV ~ ~ ~ OH ~ I N IV ~ SN I Qoo ~ ~ H HO N IH or ~ ~ H r V HI
~ ~ sveroasv ~ Ntaaor ~ ~~~~ ~ INI ~ ~ os 0 so oooo eo ~ Sos»eosro ~ ~ N ~ vo»e»t sos ~ ossoaHS ~ ~ s»rsveNINII ~~ H ross ~ ~ Oa 0 N I Ns r N I ~ HV s
«Nsossoa0»s ~ ~ ~ VS ~ ~ IH eV ~ IN ~ NH ~ I as ~ IO N ~ ~ OH ~ ~ HH Oo r
~~ av'Nv »to Nsror ~ ~~ ~ ~ ~ Hoo ~~ os otoeevo 'N ~ Ne NHHN ~ ~ Ir ~ ot 0» ~ sv sv ~ vr NON ~ Hor oat» NH ~ ~ os Hors SH No V » a IIH H»
v 00»
v~V HV OH ~ I HI »I IH
~ ~ ~ ~ '
~ ~ ~ ~ ~ 'SN ~ NH ~~ H HO N Ots ~~ H H Oe N ~ \ ~
~ ~ ovarv NSO N ~ Hor ~ ~ ~ ~~ ~ Hoe ~ Iv 0» '~ ooo N ~ soo NHHN ~ a«ev oos ~ IOt Ne ~ osr Nooo ~ ~ seor ~ os ~ H ~ sotto ~ as Hor ~~ w Ivevsoe 0»o
~ oe ~ oe 0 a0 ~ sos oooo ~ ~ oooo ~ ~ ~ ooe ~~ eeo»e ~ oeo ~ Soeo ~ oe IN IO ~ es Oeo I «oe oe sso ~ - r
~ ~ I v Ht v eoo ~ oo I H or ~ ~ ~ I ~ ~ Hos ~ I oe 0 tos o oa 0 IO I No t0 H HN ~ ~ Ias I v 0 eo I sos Ne ~ Ossa Io ~ tr ~ ~ Ho eo ~ v 0 oo ~ IOII ~ ~ 0 H or ~ ~ sw Ne ~ Oa I oa 0» e eoe
Ne H» o ~ INI ~ ~ ~ Oas I I He IOI ~ HO eeoseo sa oeo SO ate Oos ~ ~ Woe Oo N ~~ N
stoa coo» sos 0 to I esoea ~~~ I I ~ IIOII sos 0»oooo 0» esw N os oooo ~ I seat v 0 IO soot Neo vH Na aao ~ ~ SIOII I os or e ~ oos v v
I oo 00oo
N \ Ns H so t t Hv I ~ ~ OH I \ ssa sv ~ Ho I Ntt
Ne soos or ~ o H H ot rt ~ ~ sos
~
0 too coats ~ ao os ~ ~ ~ os Ho N o H
RULE - Si i i i i i8 ( i26)
~ H so g owe
e olution of the probabilities for each of the 1024 possible configurations of several length 10 cellular automata staN-
'
g om an initial ensemble containing all 1024 configurations with equal probabilities. The configurations are specified by bi a
g ose digits form the sequence of values at the sites of the cellular automaton. The history of a particular configuration is
given on successive lines in a vertical column: a dot appears at a particular time step if the configuration occurs with nonzero proba-
bi&ity at that time step. In the inst&al ensemble, all configurations occur with equal nonzero probabilities, and dots appear in all posi-
tions. Cellular automaton evolution modifies the probabilities for the configurations making some occur with zero probability yield
ing gaps in which no dots appear. The probabilities obtained by evolution for ten time steps according to cellular automaton rule
were given in Fig. 21: dots appear in the tenth line of the rule 126 part of this figure at the positions corresponding to configurations
with nonzero probabilities.
FIG. 24. Time evolution of average entropy per site for an en-
semble of finite cellular automata with X =10 evolving accord-
" Reversible cellular automata may be constructed in two (or
ing to rule 126 from an initial equiprobable ensemble. The en- more) dimensions by allowing arbitrary evolution along a line,
tropy gives the logarithm of the average number of possible can- but generating a sequence of copies ("history") in the orthogonal
figurations. Its decrease with time is a reflection of the local ir- direction of the configurations on the line at each time step
reversibility of the cellular automaton. (Toffoli, 1977a, 1980).
8 s
P ~
5 ~
6
0
P
8
ie
ii2'
i
i3
i4
i5
i6
i7
ia
i9
28
Zi
za
23
P4
25
26
27
ZB
29
38
FIG. 25. Evolution of typical initial configurations in a finite cellular automaton with N =8 (and periodic boundary conditions) ac-
cording to rule 126. Evolution from a particular initial state could generate up to 2 =256 distinct configurations before entering a
cycle and returning to a configuration already visited. Much shorter cycles, however, are seen to occur in practice.
12 ~
For example, evolution from a pair of successive configurations containing zero and one nonzero sites according to the reversible
analog of rule l 50 yields a self-siniilar pattern with fractal dimension ]ogi[4/( v 17 —3)] 84 ].
Rev. Mod. Phys. , Vol. 55, No. 3, July 1983
Wolfram: Statistical mechanics of cellular automata 627
N=B
.01—
0.001— 0.001
I I
2 10 20 2 5 10 20
.OI— .Ol—
0.001— 0.001—
I I I
After a transient of at most two time steps, the cellular 1, 3, 2, 7, 1, 7, 6, 31, 4, 63, 14, 15, 1, 15, 14, 511, 12, 63,
automaton enters a cycle, which repeats after at most six 62, 2047, 8, 1023, 126, 511, 28, 16383, and 30. Consider
further time steps. Apart from the trivial one-cycle corre- rule 90; derivations for rule 150 are similar. Whenever N
sponding to the null configuration, six distinct cycles is of the form 2, the cellular automaton ultimately
(containing nonintersecting sets of configurations} occur. evolves from any initial configuration to the null configu-
Four have length six, and two have length two. A total of ration, so that H~ —1 in this case. When N is odd, it is
29 distinct "final" configurations appear in these cycles. found that the first configuration in the cycle always con-
The number of configurations reached by evolution from sists of two nonzero sites, separated by a single zero site.
a particular initial state increases with N as shown in Fig. The nonzero sites may be taken at positions +1 modulo
26. For N=10, the maximum is 38 states, while for N. Equation (3.2} implies that configurations obtained by
N=32, it is at least 1547. Similar behavior is found for evolution for 2 time steps again contain exactly two
most other complex nonadditive rules. nonzero sites, at positions +21 modulo N. A cycle occurs
Analytical results for transient and cycle lengths may when 21 = + 1 mod N. H~ then divides Hz given by
be given for finite cellular automata (with periodic boun- 2
sord~(2)
—1 where sord~(k) is defined as the minimum j
dary conditions) evolving according to the additive rules for which 2~=+1 mod N, and sord&(k)=ord~(k)I2 or
90 and 150 (Martin et al. , 1983). A complete and general sordtv (k ) =ordz(k ). The multiplicative order function
derivation may be obtained using algebraic methods and ord~(k) (e.g. , MacWilliams and Sloane, 1977) is defined
is given in Martin et al. (1983). The additive superposi- as the minimum
—
j for which 2J= 1 mod N. It is found in
2—
tion principle implies that the evolution of any initial con- fact that HJv H~ for most N; the first exception occurs
figuration is a superposition of evolution from single for N=37, in which case II37 —H37/3. For N=k —1,
nonzero sites (in each of the N cyclically equivalent possi- ordz(k)=a, so that when N=2 1, H~ = N. Sim— ilar-
ble positions). The period of any cycle must therefore ly, when N=k +1, k — = —1mod N so that k
divide the period Hz obtained by evolution from a single =+1 mod N and ordz(k}=2a, yielding H~ —N
nonzero site. Similarly, the length of any transient must for N=2 +1. In general, if N=p&'pz'. . . , where the
divide the length Yz obtained with a single nonzero ini- are
p; primes not equal to k, ordN(k )
tial site. It is found that H& is identical for rules 90 and = lcm[ord, (k), ord, , . . . ]. ord&(k) divides the
150, but Yz in general differs. The first few values of Pl P2
H~ for rules 90 and 1SO (for N =3 through N =30) are 1, Euler totient function p(N), defined as the number of in-
Rev. Mod. Phys. , Vol. 55, No. 3, July 1983
Wolfram: Statistical mechanics of cellular automata
tegers less than X which are relatively prime to A' (e.g. , configuration. The 2' possible configurations of a finite
Apostol, 1976; Hardy and Wright, 1979, Sec. 5.5). [g(X) cellular automaton may be represented as nodes in a
is even for all X ~ 1.] y(N) satisfies the Euler-Fermat re- graph, joined by arcs representing transitions correspond-
lation I +' '— = 1 mod X. It is clear that v(n ) (q(n) ing to cellular automaton evolution. Cycles in the graph
(n —1, where vr(n) denotes the number of primes less correspond to cycles in cellular automaton evolution. As
than n, and the upper bound is saturated when n is prime. shown in Martin et a/. (1983), the transient configura-
(
If ord& (k ) is even, then ord& (k ) g(X ), while for tions for the additive rules 90 and 150 appear on balanced
ord q (k ) odd, ord q (k ) & y(X )/2. Thus II & & 2' quaternary trees, rooted on the cycles. The leaves of the
1, where the bound is saturated for some prime X. trees correspond to unreachable configurations. The
Such a H& is the maximum possible cycle length for con- height of the trees is given by Y.&;. The balanced structure
figurations with reflection symmetry, but is approximate- of the trees implies that the number of configurations
ly the square root of the maximum possible length 2' —1 which may appear after r time steps decreases as 4
.
for an arbitrary system with V binary sites. When A' is " 4
—Yv" configurations appear on cycles and may therefore
even, H, & — 2Hq;~~. Notice that ItI& is an irregu1ar func- be generated at arbitrarily large times.
tion of X: its value depends not only on the niagnitude of The algebraic techniques of Martin et al. (1983) apply
X, but also on its number theoretical properties. only to additive rules. For nonadditive cellular automaton
When H, z is prime, all possible cycles must have a rules, the periods of arbitrary cycles do not necessarily
period of one or exactly H, q. When H, z; is composite, any divide the periods H, & of cycles generated by evolution
of its divisors may occur as a cycle period. Thus, for ex- from configurations with one nonzero site. Empirical in-
ample, with %=10, H, z — 6, and in evolution from the vestigations nevertheless reveal many regularities.
2' —1 possible non-null initia1 configurations, forty dis- Cyclic behavior is inevitable for finite cellular automata
tinct cycles of length 6 appear, and five of 1ength 3. In which allow only a finite number of possible states. In-
general it appears that for large X, an overwhelming frac- finite cellular automata exhibit finite cycles only under
tion of cycles have the maximal length H, q. exceptional circumstances. For a wide class of initial
As mentioned above, for the additive rules 90 and 150, states, simple cellular automaton rules can yield nontrivial
the length of the transients before a cycle is entered in cyclic behavior. Cycles occur in complex cellular auto-
evolution from an arbitrary initial configuration must mata only with exceptional initial conditions. Any initial
divide Y,z, the length of transient with a single nonzero cor&figuration with a finite number of nonzero sites either
initial site. For rule 90, Y,& ——1 for X odd, and evolves ultimately to the null state, or yields a pattern
Y& ——D. (X)/2 otherwise, where D&(n) is the largest 2~ whose size increases progressively with time. Most infin-
which divides n. For rule 150, Yz — 0 if A' is not a multi- ite initial configurations do not lead to cyclic behavior.
ple of three, Y& — 1 if X is odd, and Y& —
— -Dz(X) other- However, if the values of the initial sites form an infinite
wise. Since, as discussed above, evolution from a11 2 periodic sequence (c.f. Miller, 1970, 1980), with period k,
possible initial configurations according to rule 90 visits then the evolution of the infinite cellular automaton will
2' ' configurations for odd X, the result Y& —1 implies
be identical to that of a finite cellular automaton with
that in this case, exactly half of the 2' possible configura- k =X, and cycles with length &&2 will be found.
tions appear on cycles. The transformation of a finite cellular automaton con-
Configurations in cellular automata may be divided figuration according to cellular automaton rules defines a
into essentially three classes according to the cir-
mapping in the set of 2 binary integers representing the
cumstances under which they may be generated. One class cellular automaton configurations. An example of such a
discussed above consists of configurations which can ap- mapping was given in Fig. 19. Repeated applications of
pear only as initial states, but can never be generated in the mapping yield successive time steps in the evolution
the course of cellular automaton evolution. A second class of the cellular automaton. One may compare the results
contains configurations which cannot arise except within with those obtained for a system which evolves by itera-
the first, say ~, time steps. For v. =2, such configurations
have "parents" but no "grandparents.
"
The third class of
tion of a random mapping among the 2 integers (cf.
Kauffman, 1969). Random mappings of K elements are
configurations is those which appear in cycles, and may obtained by choosing one of the K possible images in-
be visited repeatedly. Such configurations may be generat- dependently for each integer and with equal probabilities.
ed at any time step (for example, by choosing an initial
The mapping is permitted to take an element to itself. In
configuration at the appropriate point in the cycle, and this way, all K possible mappings are generated with
then allowing the necessary number of cycle steps to oc- The probability of a particular
equal probability.
cur). The second class of configurations appears as tran- element's having no preimage (predecessor) under a
sients leading to cycles. The cycles may be considered as random between E elements is
mapping
attractors eventually attained in evolution from any initial (K —1) /K =(1 —1/K) . In the limit K~oo this im-
plies that a fraction 1/e=0. 37 of the possible states are
The result is therefore to be contrasted with the behavior of not reached in evolution by iteration of a random map-
linear feedback shift registers, analogous to cellular automata ping. For complex nonadditive cellular automata, it ap-
except for end effects, in which cycles (de Bruijn sequences) of pears that as X~oo, almost all configurations become
period 2" —1 may occur (e.g. , Golomb, 1967; Berlekamp, 1968). unreachable, indicating that cellular automaton evolution
is "more irreversible" than iteration of a random mapping however, change discontinuously when a nonzero sc is in-
would imply. A system evolving according to a random troduced. An example of such behavior is shown in Fig.
mapping exhibits cycles analogous to those found in actu- 27, which gives the fraction of configurations visited as a
al cellular automata. The probability of a length r cycle's function of time for a cellular automaton evolving ac-
occurring by iteration of a mapping between K elements is cording to rule 126 with various values of ~, starting from
found to be a single typical initial configuration. When K =0, only six
distinct configurations are generated before the cellular
(K —1)!
automaton enters a cycle. When ~&0, the cellular au-
, (K —i)!K' tomaton ultimately visits every possible configuration (cf.
(Harris, 1960; Knuth, 1981, Sec. 3.1, Ex. 6, 11-16; Levy, Gach et al. , 1978). For ~=0. 5, one may approximate
1982). Cycles of the maximum length K occur with finite each configuration as being chosen from the 2 possible
probability. In the large K limit, the average cycle length configurations with equal probabilities: in this case, the
becomes =VvrK/8=0. 63' K, while the standard devia- average number of configurations visited after ~ time
tion of the cycle length distribution is steps is found to be 1 —([I — 2 ] )'~ = 1 —e
=V(2/3 vr/8)— —
K 0. 52' K. The length of transients Cellular automata may be viewed as simple idealiza-
follows exactly the same distribution. The number of dis- tions of physical systems. They may also be interpreted as
tinct cycles — v n/2 log. K. If we take K=256 for com- "computers" (von Neumann, 1966; Baer and Martinez,
parison with an %=8 cellular automaton, this implies an 1974; Burks, 1970; Aladyev, 1974, 1976; Toffoli, 1977b)
average cycle length -10, an average transient length and analyzed using methods from the formal theory of
=10, =94 unreachable configurations, and =7 distinct computation (Minsky, 1967; Arbib, 1969; Manna, 1974;
cycles. Cellular automaton rule 126 yields in this case an Hopcroft and Ullman, 1979; Beckman, 1980). With this
average cycle length =3.2, an average transient length interpretation, the initial configuration of a cellular au-
=2. 5, 190 unreachable configurations, and 7 distinct cy- tomaton represents a "program" and "initial data, pro- "
cles. Any agreement with results for random mappings cessed by cellular automaton time evolution to give a con-
appears to be largely fortuitous: even for large X cellular figuration corresponding to the "output" or "result" of
automata do not behave like random mappings. the "computation. " The cellular automaton rules
This section has thus far considered cellular automata represent the basic mechanism of the computer; different
which evolve according to definite deterministic local programs may be "run" (or different "functions evaluat-
rules. However, as discussed in Sec. III, one may intro- ed") by giving different initial or "input" configurations.
duce probabilistic elements or noise into cellular automata This process is analogous to the "evolution" of the se-
rules —for example, by reversing the value of a site at quence of symbols on the tape of a Turing machine (Tur-
each time step with probability ~. Section III showed that ing, 1936). However, instead of considering a single
the local properties of cellular automata change continu- "head" which modifies one square of the tape at each
ously as a is increased from zero. Global properties may, time step, the cellular automaton evolution simultaneous-
ly affects all sites at each time step. As discussed in Sec.
V, there exist "universal" cellular automata analogous to
universal Turing machines, for which changes in the ini-
tial configuration alone allow any computable (or "recur-
sive") function to be evaluated. A universal Turing
machine may simulate any other Turing machine using
an "interpreter program" which describes the machine to
be simulated. Each "instruction" of the simulated
machine is simulated by running the appropriate part of
the interpreter program on the universal machine.
Universal cellular automata may similarly simulate any
other cellular automata. The interpreter consists of an en-
coding of the configurations for the cellular automaton to
be simulated on the universal automaton. A crucial point
is that so long as the encoding defined by the interpreter
is sufficiently simple, the statistical characteristics of the
evolution of configurations in the universal cellular au-
tomaton will be shared by the cellular automaton being
FIG. 27. Fraction of configurations visited after i time steps in
simulated. This fact potentially forms the basis for
a finite cellular automaton (with W =7) evolving from a single
typical initial state according to rule 126 in the presence of noise universality in the statistical properties of complicated
which randomly reverses the values of sites at each time step cellular automata.
with probability ~. When x =0, the cellular automaton enters a The simplest encodings which allow one cellular au-
cycle after visiting only six distinct configurations. When x~0, tomaton to represent or simulate others are pure substitu-
the cellular automaton eventually visits all 128 possible configu- tion or "linear" ones, under which the value of a single
rations. site is represented by a definite sequence of site values.
(Such encodings are analogous to the correspondences be- section gives a brief discussion of the behavior of more
tween complex cellular automaton rules mentioned in Sec. complicated cellular automata. Fuller development will be
III.) For example, a cellular automaton A evolving ac- given in future publications.
cording to rule 22 may be used to simulate another cellu- We consider first cellular automata in which the num-
lar automaton 8
evolving according to rule 146. For ber of possible values k at each site is increased from two,
every 0 in the initial configuration of 8,
a sequence 00 is but whose sites are still taken to lie on a line in one di-
taken in the initial configuration of A, and for every 1 in mension. The evolution of each site at each time step is
8, 01 is taken in A. Then after 2v. time steps, the config- for now assumed to depend on its own value and on the
uration of A under this encoding is identical to that ob- values of its two nearest neighbors. In this case, the total
tained by evolution of 8 for ~ time steps. If cellular au- number of possible sets of local rules is k' '. Imposition
tomaton 8 instead evolved according to rule 182, 01 (or of the reflection symmetry and quiescence "legality condi-
10) in A would correspond to 0 in 8,
and 00 to 1. The tions" discussed in Sec. II introduces —, k (k —1)+1 con-
simplicity of the interpreter necessary to represent rules straints, yielding k~ ''+ ' '~ "legal" sets of rules. For
146 and 182 under rule 22 is presumably responsible for k =2, this implies 2 =32 legal rules, as considered in Sec.
the similarities in their statistical behavior found in Sec. II. The number of possible legal rules increases rapidly
III. Figure 28 gives a network which describes the simu- with k. For k=3, there are 3' =129140163=1.3)&10
lation capabilities of the complex elementary cellular au- rules, for k =4, =3)& 10, and for k = 10, 10
tomaton rules using length two linear encodings and with As a very simple example of cellular automata with
the simulated rule running at half the speed of the simula- k ~2, consider the family of "modulo-k" rules in which
tor. Many of these complex rules may also simulate sim- at each time step, the value of a site is taken to be the sum
ple rules under such an encoding. Simulations possible modulo k of the values of its two neighbors on the previ-
with longer linear encodings appear to be described by in- ous time step. This is a generalization of the modulo-two
direction through the network. Not all complex cellular rule (90) discussed on several occasions in Secs. II— IV.
automaton rules are thus related by linear encodings of Figure 29 shows the evolution of initial states containing
any length. a single site with value one according to several modulo-k
As discussed in Sec. V, the elementary cellular automa- rules. In all cases, the pattern of nonzero sites is seen to
ta considered here and in Secs. II and III are not of suffi- tend to a self-similar fractal figure in the large time limit.
cient complexity to be capable of universal computation. The pattern in general depends on the value of the
However, some of the more complicated cellular automa-
"
ta described in Sec. V are "universal, and may therefore
nonzero initial site, but in all cases yields an asymptotical-
ly self-similar figure. When k is prime, independent of
in principle represent any other cellular automata. The the value of the initial nonzero site, a very regular pattern
necessary encoding must be of finite length, but may be is generated, in which the density T(n ) of "triangle struc-
very long. The shorter or simpler the encoding, the closer tures" is found to satisfy a one-term recurrence relation
will be the statistical properties of the simulating and yielding a fractal dimension
simulated cellular automata.
V. EXTENSIONS Dl = logi
k
gi = + logi
1
k+1
2
]
of Secs. II —
so that D& —1+ log32=1 631, D&-1 683, and so on.
The results have for the most part been
IV
restricted to elementary cellular automata consisting of a
When k is a composite number, the pattern generated de-
sequence of sites in one dimension with each site taking
pends on the value s of the initial nonzero site. If the
on two possible values, and evolving at each time step ac-
greatest common divisor (s, k ) of k and s is greater than
cording to the values of its two nearest neighbors. This
one (so that s and k share nontrivial prime factors), then
the pattern is identical to that obtained by evolution from
an initial site with value one according to a modulo-
k/(s, k) rule. In general, the density of triangles satisfies
a multiple-term recurrence relation. In all cases, the frac-
tal dimension for large k behaves as D-2 —1/log2k [as-
suming (s, k) «k]. When k~oo, the values of sites be-
come ordinary integers, all with nonzero values by virtue
FIG. 28. Network describing simulation capabilities of complex of the nonvanishing values of binomial coefficients, yield-
elementary cellular automata with length two pure substitution ing a figure of dimension two.
or linear encodings. Cellular automata evolving according to All modulo-k rules obey the additive superposition
the destination rule are simulated by giving an encoded initial principle discussed for the modulo two in Secs. II and III.
configuration in a cellular automaton evolving according to the The number of sites with value r after evolution for ~
source rule. Representability of one cellular automaton by
',
steps from an initial state containing a single site with
another under a simple encoding implies similar statistical prop-
value one is found [on analogy to Eq. (3.2)] to be
erties for the two cellular automata, and forms potentially the
=2 g, r) where the function g([k])(r) gives the num-
[A' j
(~) ~
C5. cd
(A
CP
U
O O
E ~ M
~
c/l
~ ~
~ ~
~ ~ ~ OA
~ ~
~
~ ~
~ (LP
cd
8 00
0
~ ~
~ ~
~ ~
IQ
IEJ
~ ~
~
~
~
~
~ ~
~ ~
'~
Q
~ ~
III
N
4l
0 ~ ~
e
Q E
a ~ ~
bQ cd O
N
N
~ ~
0 0
0
I
G
0
Sa
N ~ ~
a
0
~ I ~ ~
~
~
~
~ (0
ID ~ ~ ~ ~ ~ ~ ~ ~
~ ~
III
I C ~
~
~
~
~
Ia O
~ ~
~ ~ cR
~ ~ ~ ~
~ ~
~ ~
IQ ~ ~
ID a ~ ~
~ ~
III ~ ~
~ ~ cd
Cl
~ ~
~ ~
O
~ ~
O
AI
'3 CJ cd
8' 40
4 «1 ~ ~ 440 0F ~ 0P0
h « I ~
~ ~' 8 0 ~ 4« 8 ~
41'ePP0 ~
0 1 ~ 8 8 0 8 0h«Ah«ha«111
'8 F 8 040 '~
~ 1 ~ 8 44 ~ I ~ 8 8 AA ~ ~ 0 ~ OPS
PP ~1«««A«AI, 11 bQ
~ I
cd
~ ~
~
~
~
~
I ~
~ ~
~
~ ~
~ ~ bQ
~
~
~
~
~
~ ~
~ ~ ~ I ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
O
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~ 0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~
I~ ~ ~ ~ ~ Q
~
~
~
0 ~
~
~
~
~
~
~
~
~
~
~
~ ~
~
~
~
~
~ ~
~
~ I~
~
cd E
5I
~
~
~ ~ ~ ~ ~ ~ ~
~
~
cd
~ ~ ~
O
o ~
~ ~
~ ~ ~
~
'~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
N ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
N ~ ~
0
I
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~
~
~
~
O Q
~
~
~
~
~
~
~
~
0 ~ ~ ~ ~
\ ~ ~ ~
~ ~
~ ~
~ ~
~
~ ~
~ ~ ~
~ ~ ~
~
~
~
~
~ ~
O
~ ~ ~ ~ 0 ~
N ~ ~ ~
~ ~
~ ~
~
~ ~
N ~ 0
~ ~ ~ ~ ~ ~ ~
~ I ~ 0
~ ~ ~ ~
Cl ~ ~ ~ ~ ~
~
I ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~
0
~ I 0
~ ~
I~ CP
N ~ ~ ~
~ ~
~
~ ~
I~ ~
~ ~
~
~
~
~ ~ ~ ~ ~ ~ ~
cd
4l I~
N
~ ~
0 ~ ~
~ ~ ~ ~
~ ~
~
~ ~ ~ ~ ~ ~ O
~ OA
~ a
I
~
~
~
~ ~ ~ ~ ~ ~
al ~ ~ ~ ~ ~ ~
~ ~ ~ ~ a ~ ~ ~ ~
~ 8 ~ ~
IS ~ ~
~ ~ ~ ~ ~ ~
I~ ~
~
~ ~
~ ~
~ ~ ~ ~ ~ ~
U
40
a
'3 0«101014««1«A«11«14
. 0 0 0 ~' 8 ~ P ~ - ~ F 8 ~ 011JFJOS ~ 4 ~ FJ OPSI«Ah«illa
A ~ O'8 ~ ~ PO
a, Oh ~ FJ ~ 4h«111«I 0 1 ~ F J 044 1 8 04 ~
JI' hlm
O
cd
~ ~ I ~ I ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
I ~ M
~ ~
~ ~
~
~
~ C O
cd
~ ~ ~
O CJ
0
~ ~
0
~ ~ ~
~
~
~
V)
0
~
5I
~ ~
~
~ ~
~ ~
0 ~ 0
O
~ ~ ~ 0
~ ~ ~ ~ ~ ~ ~
0
e
~ ~ ~ 8
~ ~ I bQ
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~
al ~ ~ I 0 0 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ bQ O
~ ~ ~ ~ ~ ~ ~ ~
N
~ ~ ~ ~ ~ ~
a O CA
al
~ ~ ~ ~ ~ ~ ~ ~ r ~
~ ~ ~ ~ ~ 0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
l9
Cl
~
~
I
~
0 ~ 0 0
~ ~ ~ ~
Q
~ ~ ~
I ~ ~ ~ ~ ~ ~ ~ ~ ~
~ M
IS ~ ~ ~ ~
0
~ ~ ~ ~ ~ ~ 0 cA cd
ID ~ ~ ~ ~ 0
I
I ~ 0
J
lm
~ ~ ~ ~ ~ I ~ ~
I ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ CP
Cl J 0 ~ ~ ~
a
bQ
~ 8 ~ ~ ~ ~ ~
O
a 4 '1 ~ PJ ~4 ~ AA ~ P8 OPS11111111«11
I ~P 144 014844 ~ 04111 0 ~ Ar ~ 4 ~ op ~ ~ reps
1 ~ ««Ah«4 ~ Sh ~ POOP««r«1«11141
0 0 0 ~ h F 8 OF ~ ~ 8 8
cd
a Q O
O
'U
~ M
cd
U
O U
0 0 0
0 ~ ~ 0
.~
8
Q cA
J 8
0
o U
cd
.8
O
I e
I 0 0
cd U
aN
CO
8 0
8 0 ~
e
0
8 ~ ~ cd
0
t5.
Ia 0 G
I 0
QJ
IS '~ E cd
E
cd O O
0 hl 810 ~ 0 ~ 1 ~
~ pp 040Ahalhhhhh
hArp 0 00 ~~ 40 AA ~ 1 Ja 00 ~ 1 P 8 0 1 1 «1«Ah«441
0 ~ hhl ~ P 8 00 4 011 PJI'SP
ohpaopa001118 ~ ~ ~ ASF ~ 044
~ 11«1«R SAAIFJ0 ~
~ P 8 0 ~0 1 ~
«A«Ah«Ah
)
CJ
cn
cd
O O
Q
cf)
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 'I ~ ~
~ ~ ~ ~ ~
I ~ ~
~ ~
~ 0
~
~
~
~
~
~
~
~
~
I ~
~
~
~
~
~
~
~
~
a
~ ~
~ ~ ~
~ ~
~ ~ ~ ~
~
~ ~ ~ ~ ~ ~
~
~ ~
~ 5 ~ ~ ~ ~ ~
I ~
~ ~ ~
~
~
~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
Q cd O
~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ e ~ ~ ~ ~ ~ ~
~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I
~ ~
~
0
~
~
~
~
~
e ~
~
~
~
~
~
~
0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Q Ll
~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
I ~ ~
~ ~
~ ~ ~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
0
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
0
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
I
O
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ 0 ~ ~ ~ ~ ~ ~ 0 ~
~ 0
0
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
0
~
~
~ ~
~
~ ~
~ ~
~ ~
~ ~
~ ~ ~ ~ ~
~ ~
~
~
~ ~
~
~
~ ~
~
~ ~
~ ~ ~
\ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~
I ~
~ ~ ~ ~
~
~ ~
0
~
~ ~ ~
~ ~
~ ~ ~
~ ~ ~
~ ~ ~
0
~ ~
~ ~ ~
~
cd Q
~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ 0 ~
~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~
ID ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
I I ~ ~ ~ ~ g ~ ~ ~ ~ Ch
~
~
~
~
~
~ ~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~
0 0 ~
~
~
~ ~
~ ~ ~
~
~ ~ ~
0 ~
~ ~ ~ ~ ~ ~ ~
I ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ 0~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~ ~ ~ ~
~
~
~
~
~
~ ~
~
~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
I ~ ~ ~ I~ ~ ~ ~ ~
~ ~
I ~ ~ bQ O
e ~ ~
~ ~ ~
~
I ~
0 ~
~ ~
0 ~ 8 ~ ~'
~
~
~
~
~
0
~
~ ~
~ ~ ~
~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
0
'I~
~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~~ ~ ~~ ~ ~~ ~~
~ ~
~
~
~
0 ~ PAI
~
o
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
0 ~ ~ ~ \ ~ ~ ~ ~ ~ ~ a ~ a 0 ~
0 ~ ~ ~ ~
a ~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
0
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
0
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~ ~ a
~ ~
~ ~
~ ~
0
~ I ~
~
~
~
~ ~
~ ~
~
~ ~
~
~
J
~
~ ~
~ ~ ~ ~
~
~ ~
~ ~ ~ ~ ~
I ~ ~~ ~ 0~
~ ~ ~ ~
~ 0
~ ~ ~
~ 0 ~ ~ 0
~ ~ ~ ~
~ ~
~ ~
~
~ ~
e
~ ~
~ ~ ~
~ I
5I !
R
~
~ ~
~ ~ ~
~
~ 0
~ ~
~ ~
~ ~ ~ ~ ~ 'I
'0 ~ ~
~ ~ ~
~
~ ~ ~
~ ~
~
~
~ ~ ~
~ ~
V3
f 1 cd
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ $
~ 0
~ ~ ~ ~ I ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 0 0
~
~
~
~
~
~
~
~
0
~ ~
~ ~
0
g
~ ~
g a ~
~
~
~ ~ ~
~ ~ ~
0 0
g ~ ~
~ ~
I ~
~ ~
~ ~ ~
I~
~
~
~ ~
~ ~ ~
~
at bQ
~ ~ ~ ~ ~ ~ 0 ~ ~ ~
~ ~ ~ ~ ~ ~ I ~
0 I ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ e ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~ ~ ~ ~ ~ 0 ~ I
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 8 ~ ~ ~ '~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~
~
~
~
~ ~
~ ~ ~ ~
~ ~
~ ~
~
~
0
~
~ ~
~
0
~
~
I 0
~ ~
~
~
a
~
~
~
~ ~
I ~ ~
e
~ I
~ ~
F 5
~ ~
~ ~ 0 ~ ' OP
~
~
~
~
~
8
~
~
~
8 ~
~ ~
~ ~
~ 0 a ~ 0
~
I 0
~
~
~
~
~
~
8
0 ~ ~ 0 I ~
8 0 ~
~
I~ 0
~ ~
~
~
~
~ 0 ~ ~
I
~
~
0 I
0 ~ I
cd O
~ ~
~ ~
~
~
~
~
~
~
~
~
~ a
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
I ~
~
~
~
~
~ ~
0
~ ~
~ ~I ~ ~
ce
~ ~
~
~
~
~
~
~
~
~
~ I
~
~
I ~~ ~ ~~
~
~
~
~
~
~
~
0
I ~ ~
~
0
~
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
J 0 ~ ~~ ~ ~~ ~ ~~
~
~ 8
~ ~ ~
0
~ ~ O ~ PAI
~ ~
~
~ ~
~ ~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ cd
~ 00
~
Q
~ «1 ~ PJ 40 11 ~ P 8 ~ 040
1 ~ PJIO Ah«A«Ah«A«R 0
01 ~ JSP«h«AA«1 ~ F 8 1~ 4 ' F I 0~ 1 ~ ' ~ FJ'48'Oh '8OPI
«11111«l ~ ~
~
~ M ~ ~ cd
Q m
C
cd
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ 4 ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ 4
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
4 ~ ~ ~ ~ ~ ~
~
~
~ ~ ~
~
~
~
~ ~
~ ~
4
4
~ ~ ~
~ ~ ~
~ ~ ~
5
~ ~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~ ~
~ ~
N ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~
N ~ ~ ~ ~ ~ ~
4
N
~
~
~
~
~ ~
~
~
~
~ ~
~ ~
~ ~
4
~ ~
4
5 ~
4
~
~ ~
5
4 ~ ~ ~
~ ~
~ ~
~
~
~
~
4
~
~
~
~
4 ~ ~
~ ~ ~ ~ 4
~ ~ ~ ~
~ ~
~ ~ ~
~
~
~ ~
4 ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~
4N ~
~
~
~
~
~ ~
~ ~
~ ~
~
~
~
~
~
~
~
~
~
~ 4 ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~
~
4 4
~ ~ ~ ~
~ ~
~ ~
~ ~
~
~
~
~
~
~
~ ~
~
~
~ ~ ~
~
~ ~
~ ~
N ~ ~ ~
~
4
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
4 ~ ~
' ~
~
~
~
~
~
~
~ ~ ~ ~
4 ~ ~
~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~
~ 10 ~ FOI ~0~
11 ~ I ~ 4000%1 ~ 0$ I ~ 0
1%%%SIC«5 ~~
~
~ II ~ $0%0 ~ ~ 11400 0001111%111%%)
11 ~ I ~ ~ 0 ~ ~ 14$ ~ ~ 0$-11111%
I I $$0 ~ ~ 4 04 0 ~ F~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~
~
~
~ ~ ~
~ ~ ~
~ ~ ~
~ ~ 4
~ ~ ~ ~ ~ ~ ~ ~
~ ~
~
)
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ 5 ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4
N
~ ~ ~ 5
~ ~
5
~ ~
~ ~
~ ~ ~
~ ~ ~
~ ~ ~
~
~
~
~ 5 ~
~ ~ ~
~ ~ ~
~
~
~ ~ ~
~
~
~
~
~
~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4 ~ ~ ~
~ ~ ~ ~ ~
) ~ ~
~ ~
~ ~ ~
~ ~ ~
~
~
~ ~ ~
~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~
4 ~
~ ~
~ ~
~ ~ ~
~ ~ ~
~ ~
~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~
~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~
4 5 ~ ~ 5
~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~
~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N
~ 4
~ ~ ~
~ ~ ~
~
)
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4
N
~ ~ ~ ~ ~ ~ ~
~ 5 ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ '~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N )5 ~ ~
~
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~ ~
~
~ ~
~
~
~ ~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~
~
~
~
~
~ ~
~
I
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ 4 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~
0$ ~
~ 11 ~ 0 ~ \ 00 CI8%1 54CICER ~ 11 ~ FS 0$ 0 «I ~ FS
~
~ 0~ %1 ~ ~ ~
%%%%%%%%«IR $$0 01 I ~
~ ~0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
) ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 4 ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4 ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
)
'~
~ 5 '5
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
eN ~
e) ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 7 ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N
~
5
'~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ 4 ~
~ ~ ~
~
~
~ ~
) ) ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~
~
4
N
5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4hl ~
)
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N '5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~
~
4 ~ ~ ~ ~
N ~ ~ ~
4 ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~
~ ~ ~ ~
~
~
4
~ ~ ~
~
~
~ ~ ~ ~
~
~ ~
4 ) ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ 4
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~
00
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N
e ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~
I0 ~ 0 ~ ~ I ~ FS ~ 040\1
I I I I IFe1% ~~ I~ 0I ~
11 ~ Fe 0 -I ~ 4 ~~ 0$ C«
~ 1%~ ~r I~ 0~0 II~ 0~ ~ 0~
II ~ ~ 00 ~0
~ I ~ F 0 0 ~ 0I
~ ~ ~ 0 ~0 %%1 ~ ~
~ ~ ~
~ 4
~ ~
~
)~ 5 ~
~
~
4
~
~
4
~
~
~ ~
~
~ ) ) ~ ~
~
~ ~
~
4
~
~
) ~ ~ ~
~
~
~ ~ ~
~
~
~
~
~
~
~
~
~
~
~ ~ 5 ~
5 ~
I~I ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ e ~ ~
~ ~ ~ ~ ~ ~
~ ~ 5 ~ ~ ~ ~
~ ~
~
4 ~ ~
~ ~
~ ~
~ ~
~
~
~
~ ~
~
~
~
~ 5
'~ 5 ~
'~ ~
~ ~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ 4 ~ ~ 4 ~ ~ ~ ~ ~
l4 ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~
N ~ ~
~
~ ~ ~ ~ ~
) ~ ~
~
~
~
~
~
~
~
~
~
~
~ '~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~
~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
III ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~
44 ~
~ ~ ~ ~
5 I ~ ~ ~ ~ ~
N
44
~ ~
~
~ ~
~
~
~
~
~ ~
5 ~
' ~
~
~
~
~ ~ ~
~ ~ ~ ~
~
~ ~
~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
N ~
e
II4
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~
~ ~
~ ~
~ ~
N ~
~
~
~
~
~
~
~
~
~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
44 ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~
~ ~
0 «I Fe I ~ ~
I ~ ~ r ~ I ~ ~I ~ ~ r ~ 040
~ I4 ~ r 4 ' 0 ~
~ I ~ F~ 0$%«1%%%«I\I
00 I IF 0 ~ 4 ~ ~ r 4
~ I ~ ~ '40 ~
~ - r ~ ' I ~ 0I«'«%%«k
r ~ 4 ~ ~ 4
~ ~ ~ ~
~ ~ ~ ~
'~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~
4
hl
~
~ ~ ~
~ ~
~
4
~
~
~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
N ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ 5 ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
414 ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
l4 ~ ~
hl ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
N ~ ~ ~ ~ ~ ~ ~
~
~
~ ~ ~
4
hl
~
~
~
~
~ ~
~ ~ ~ ~
4 ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~
84
~ I ~ ~ ~ 0$ 0 - ~ eeee'$4$
«I - - %1 0~ ~ ~ ~ I~I ~ ~ ~ ) 4%44 ~~
~ ~ r ~
-\%\%1
$4 - ~ ~ 0 ~ I ~ ~ I4 I . ~ I ~ 4 ~ r 4
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ' ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~
~ ~
~ 'I
~ ~
0 ~ ~
0
~ ~ I 0 ~ 0 ~ ~
~
~
~ ~
~ ~ ~ ~ ~ ~
~
~ 0 I ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ 1
~
~ 0 ~
~ ~
~ ~ ~ ~ ~
4 ~ ~ ~~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ '
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~
~ ~ e 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~ ~ e ~ ~ ~ ~ ~ ~
~ ~ 0 ~ ~ 0 ~ ~ ~ ~ 4 ~ ~ ~
J~ t
~ ~ ~ ~ ~ ~ ~ 4
~ ~ ~ ~ ~ ~ ~
~
~
~
~
~
~
~
~
~
~ ~
I I ~ ~ 4
~
~
~ ~
~ ~
~
~
~
~
~
~
~
~
~ ~
~ ~ I
~
~ ~
~
~
~ \ ~
I~
~
~ I
~ ~ ~ ~ ~ ~ 'I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 4
~
~ ~
~
~
~
~
~
~
~
~
~ ~ ~
~ ~
~ ~
~ ~
~
~
~
~
~ ~ ~ ~
4 ~
~ ~
~
~
~
~ 4
~
~ I ~ r ~ ~
I
CD '~
~
~
~
~
~
~
0
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~
~
~
~
I ~ ~
~
0
~ ~
~ ~ ~
~
sI~ ~ ~ ~
~
~
0
~ ~
~ ~ ~ ~
~
~
~ ~
~
I
~
~
~ ~ 4
'~
~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ I ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~
~ ~
~ ~ 0 ~
~ ~ ~ 0 ~ ~ ~ ~ 4 ~
~ ~ ~ ~ ~ ~ ~ ~ ~
0 0 ~ ~
~ ~ ~ ~ ~ ~ ~
IV a ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~
II
~ 0 ~ ~ ~
~ ~ ~ ~ 0 ~ ~ ~
~ ~
~ ~
~
~
~
~
4
~ ~
~
~
~
~
~
~
~
~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~
~ 4
~
~
~
~
~ ~ ~
~ ~ ~
e ~
I~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ a
CV ~
~
~ ~ ~ ~ 4 ~ ~
~
~
~
~
~ 0 ~ ~
J a ~ ~
~
~ I~ ~~ I ~ ~ ~
~ ~
~ ~
~ ~
4 ~ ~ ~
~
~
~
~
1 ~~ J
I ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
CV
~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ I~ ~ ~ ~ ~ ~ I ~ 4 ~ ~ ~ ~
~
~
~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~
I ~
~
~
~
0
~
~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~ ~ ~ ~
~ ~ ~
~ ~
~ ~ ~
e ~ ~ ~ 4
0
~
~ ~
~
~
'I
~ ~ ~
~ ~
~
~ ~ ~
4 ~
~ I
~
~ ~
~
0 ~
~
~ ~ ~ ~
~
~
~ ~
~
~
~
~ ~ ~ ~
~
~
~ ~
~
~
~
~
~ ~ ~
~
~ ~
~
~
~
0
~
~
~
~
~
~ ~
~
e
~
~
~
~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
0
0
Sa ~
~ ~
~ ~
~ ~ 0
~ ~
I ~ I I
~
~
IS
~ ~ ~
~ I I I ' ~ ~ ~
~ ~ ~ ~
~ ~
~
~
~ ~
~ ~
~ ~ ~ 4
~
~
~ ~ ~
CD
~
~ ~
~
~ ~
~ ~
~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~ ~
~
~
~
~ ~ ~
~
~ ~ ~ I ~ ~ I ~ ~
~ ~
~
~
~
~
~
~
0 ~
~
~
~ ~ I ~
~ ~
~ ~
~ ~
~
~
4
~
~
~ ~
~ ~
~
~ ~
~
~
~
~
IV ~ ~
~
~
4 ~ ~ ~ ~ ~ 0 ~
~ ~ ~ ~ ~ ~ ~ ~ a ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~
I ~ ~ ~ ~ ~ ~ ~ ~ ~
~
Al ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 3 ~ I I ~ ~ ~ ~ ~ 4 I ~
'I . I
~ ~ ~ ~ 0 ~ 4 ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
CD ~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
I I4 ~ ~~ ~ ~ ~
~
~
~
~ ~ ~ ~
~
0
~ Ia ~ ~ ~
~
I~ ~ ~
~
I
~ 0 0
0
~
~
~
~ ~ ~ 4 ~
4
~ ~ ~
~
~ ~
~ ~ ~ ~
~: ~
I
~
0 ~
~ ~ ~
e
~ ~
~ ~
~ ~
~ ~
~ ~ ~
4 ~ ~ ~
~
CV 4 ~ ~
~
~
~
~
~
~
~ ~
~ ~ ~
~
~
~
~ ~
~ ~ ~
~ ~ ~
I ~ ~ e ~ ~ ~
~ ~
~
~ ~
~
~
~ ~
~
~
~
~ ~
~ ~ ~
0 ~
~ ~
~
~ ~
~ ~
CV ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~
0
~
~
~
~
~
~ S
~ ~
~ ~
~
~
0
~
~ ~ I
~ ~ ~
~ ~ ~
~
~
~
~
~
~
~ ~
I~ ~
~
~ ~ ~ ~
CV ~ ~ ~
CV ~
~
~
~
~
~
I ~
~ ~
I 4
~ ~
~ ~
~ ~ ~ ~ ~ ~
ID ~ ~ ~ ~
~ ~ ~
'~ ~
0 4 ~
~ ~ I ~ ~ ~
I ~ ~ ~ ~ ~ ~ ~
~\
~
~
~
~
~
~
I 4 ~ ~
a ~ ~ ~ ~
~ ~
~
~ ~ ~ ~
4 ~
~ ~
a ~ ~ ~
~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ 4 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
J ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~
~ ~
~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
0 4 ~ ~ s ~ $04444144444
~ ~ a ~ pg
1 000 4 5 05~
4101st ~ 0 441%1 ~ pps h441
her ~ 444
~
0 4 ~~ 4 0
4 ' ~ r ~ ~
44444 0 5 SP" 444hhhhh
~
~ ~ ~ h ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~
~ ~ I ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ 4
~ ~
~ ~
~ ~
~
~
~
~ ~
~ ~
~ ~ ~
~ ~
~
I I ~ I ~
~ ~ ~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ 4 ~ ~ I ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ I ~
~ ~ ~
~
~ ~
~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~
~ 0
~ ~ ~ ~
~ ~
~ 4 ~ ~
~ ~ ~ ~
~ ~ ~ ~
S ~ ~ ~
~
~
~
~
~ ~ ~ ~
~ ~
~ ~
~ ~
\ ~ ~
~ ~ ~
~
~
~ ~ ~ ~ ~
~ 0 C
~ ~ ~ ~
~ ~ ~
~ ~
~ ~
I ~
~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~
~ \ ~ ~ ~ ~ ~
1 ~
~
~
~
~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~
~
0 ~ ~ ~ ~ ~
~
~ ~ ~
~ ~ ~
~ ~
~ t
~ I ~ ~
~ ~ J I ~
~ ~
~
~ ~
~ ~ t ~ 0 ~ 0 ~ 4 0 0
~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
0 ~
~ ~ ~ ~ 1 0
~ » ~ ~ \ 4 0
0
~ ~
0 t S ~ ~ ~ ~
~ ~
0 0
I~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
4 ~
~
~
~
~
\ 0
ass.
~ ~ ~ e ~
0 ~\ ~ 0 ~ ~ ~ ~
ID
0 1
~ ~ ~ ~
0 ~ 0 1
~
~
~
~ ~ ~ ~ ~
~ ~ 0 4 ~ 4
~
~
t tt ~ ~ 4 ~
4 0 0 0
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ \ ~ ~ 0
I ~ 1 ~
~ \ 0 ~ ~
I I
~
~ 4
I
4 ~
1~ ~ 0 ~ ~
0 0 0 ~ ~\ ~0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 0 ~ ~ ~ 0 ~ ~ ~ 0 4 4 ~ ~ ~ ~ 4 0 ~ 0 ~
~
0 ~ ~ 4 ~ 4 4 ~ ~ ~ ~ 1~ 4 ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ a ~ ~ ~ ~ ~~ 0 ~ ~ ~ ~ ~ 0 ~ a e ~ ~
~ ~ J I ~ ~ 0 0 0 ~ ~ 1 0 ~ ~ ~ ~ ~ ~
~ ~
~ 4 ~ ~
~
~ ~
0 4 t~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ 1
CV ~ ~
~ 1 ~
0 ~
~ ~ ~
~ I
~ ~
~ ~ ~ ~ 4
~
0
~
~
0
~
~
~
~
~
4 ~ ~
00
0 ~ ~ 0
~ ~
~ e ~
~
I ~
~ ~ ~ 4
~ ~
~ ~ ~ ~ ~ ~ 0
CV ~ ~
~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~
~ ~
~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ J I
CD ~ ~ ~ ~ ~ ~ ~ ~ ~ a
~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
'~
~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ '~ ~ ~ ~ ~ ~ ~ I ~ ~ ~
CV 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I 1~ ~ ~ ~ ~ ~ 0
~ ~
~ ~ ~
~ ~
~
~ ~
~
~ ~
~
~ ~
~
~ ~
~
~ ~
I~ ~~ ~ ~~ ~ ~~ ~~
~ ~
' ~
~
I ~
~
~ ~
4
4
~
~
~
~
I ~ ~
~
~
~
~
~
~ ~
~ ~ ~ ~ 0
~ ~ ~ ~ ~ ~ ~ ~
~ ~
~
~
~ ~ ~ ~ ~ ~
~
~ 0 ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
OJ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~
CV ~ ~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~
~
~
~
~ ~ ~ ~ ~ ~
~ ~ ~ 0 ~
~ ~
~ ~ ~ ~
J ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
I ~ ~
~
~ ~
~ ~ ~
~ ~
~ ~ 4 ~
I ~~ ~ ~ 0 t ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
CV ~ ~ ~ I ~ ~ ~ ~ ~
~ ~
~ ~ 0
~
0
~
~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 0 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ e ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
CD ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
CD ~ ~ ~
~ ~
~ I ~ ~ 0
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ I ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ I ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
CV ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
CV ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 'I ~ ~
CII ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
4
~ ~
~
~
~ ~
~ ~
~
0 ~
~ ~
~ ~
~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ e ~ ~
~ ~ ~ ~ ~ I ~ ~ ~
CII
~ ~ ~
~ ~
~ ~ ~ ~ ~
~ 4 ~ ~
~
~
J I~ I ~ ~ ~ ~ ~ 1
~ ~ ~ ~ ~ ~ ~ I 0 ~ ~ I~ ~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
CV
~ ~
~ ~ ~ 4 ~ ~ ~ ~ ~
ID ~ ~ ~ ~ ~ ~ ~
~
~
~
~
I ~ ~ ~ ~
~ ~ ~ ~ I ~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ S ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 'I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ 0 ~ ~ 4 ~ ~ ~ ~ 4 ~
~ ~ ~ ~
I 0 ~
~
I ~ ~ ~ ~ ~ ~
4 ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~
I~ ~ ~
I' ~
~ ~ ~ ~
~ 0 ~
~ I
~
~ ~ ~
~ ~ ~
~ ~
~ ~
~ ~ 4
4 ~ ~ ~
~ ~ 0
~
~ ~
I ~
I ~ ~
I ~
~ I
~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ a 0 ~ ~ 4 ~
~ ~ 'I ~
~
~
~
~ ~ ~
0 ~ ~ ~
~ ~ ~ 'I ~ 0
0 4
0
~
I
~
~ '~
~
'~ ~
~ ~ ~ ~ I IS'I ~
~ ~ I
~
~
~
~
~ ~
~
~ ~
~ ~
~
4
~ ~ ~
~
~
~ ~
~
~
~
~
e
~
~
I
4
~
~ ~ ~
~
~
~
~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~
I~ ~ ~
~ ~ ~ ~ ~ C
~ ~
~ 0
0 ~
a
CV ~ ~ ~ ~ ~ 4 ~
II~ ~ ~
~ ~ ~ ~ ~ ~
I e ~ SI IIS ~ ~
~ ~
4
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~
~ ~ ~ I' 0 ~
CV
Dl ~ ~
0
e
0
~ ~ 'II I I~ 'SS Ie ~ ~
' ~
I
~
ST ~
III ~ ~
~ ~ ~
~ ~
~
~ ~ ~
~ ~ ~ ~
0
~ ~
~ ~ ~ ~
CV 0 ~
~
~ ~ ~
~ ~ ~
I ISi ~ ~
~
~
~
~
~ ~
~
~ 4
~ ~ ~ ~
44
~ ~
~ ~
~ ~
4 ~ ~ ~
J ~ ~ ~ 4
CV
SI 4 4 ~
I~ J ~ ~ ~
4 I I~ ~ 0 ~ ~ ~ ~
~ ~ ~ ~
0 ~ a ~
4 a ~
4 ~ ~ ~ 0 ~ ~
~ ~ ~
CV
~ ~
e
~ ~
a
~ ~
~ ~
~ ~
~ ~ ~ a ~ ~
~ ~
~
~ I ~ 0
~ ~ ~
~ 4 ~ ~ 0 ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
0 ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~
CV ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 4 ~
CD
CV
~ ~
~ ~ ~ ~ ~ ~ I ~ ~ ~ ~
~ ~
0 ~ ~
Isa' II 4
4
4
I I
OC
~ ~ 0 ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~~ ~ ~ ~
CV
~ 0
~ ~ ~ ~ ~
I
~ ~ ~
~ I
~
~
~ ~
~ ~ ~
I ~ ~
~ ~
~
~ ~
~ ~ ~
~ ~
0 ~ ~
~ ~ ~
~
~ ~ III ~ ~
CV ~ ~
~ ~
~ e
~
\ ~ ~ 0
~ ~
~ ~ ~I~
~ ~ ~
I '
~ ~ ~
I. ~ ~ ~ ~
~ ~
~ I 0 '~
~ ~ ~ ~
~ ~
0
~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ 4
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~
h ~ ~ 0 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
441%tra ~ ~ 04111141014%
1 50 40041
~ sp I ~ ~ ~ pa
~ ~ 1 ra 0 00 ~ 41 -~ I s " ~ 0111
4th 44f 4
I ~
~
~ CiCR ~ '110$ ~ I'004111114441$
000 arhrss 050 ~ %Chess ~ ~
011 ~ 50 ~ 0$414J411111
105$ 0$ 54 ~ J ~ 4 ~ ~ 4~ 0
~ ~
0 ~
~
I,jiI.
~
0 ~
II ~ I
~
ji i ~
I ie II
e ~ I
CD
Cl jS ~
~
~
J
~ ~
i' I :Ss i
~
CV ~ ~
~ I '~
~ ~ ~
~ ~ ~
~ ~
~ ~ ~ 4 ~ ~ ~ ~
i r ~ ~ ~ ~
~ ~
~
CV I~ ~ ~
~ ~
~ ~
CD ~ ~ ~ ~ I ~
CD
CV
~ ~ ~ ~ ~ ~ ~ ~ S
~ ~ ~ ~ ~ ~
CD
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
IV
CD I ~
CD
~ ~ ~
4 ~ ~
~ ~
CD ~ ~
~ ~ ~ ~
CJ ~ ~ ~
IJ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ a
CD ~ ~
~ h ~ ~ ~ ~ ~ ~
~ ~
4
~ ~
4 0 04%5005 0 - 4 0
0 05S
- ~ ~ % ~ 0 ~
s ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 4 ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ S ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~
S ~ ~ h ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ h ~ ~ ~ ~
~ 4 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~
~ ~
I~ I ~
I ~
~
~
~ ~ ~ ~ ~ ~
~ ~ 'I ~ ~ ~ ~
4 ~
~ ~
~ ~ ~ ~
~ ~ ~ S ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ a
4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ h ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
~ ~
~
~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~
~ ~
~ ~
I ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~
~
~
~
r ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ a ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ 0 ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ a ~ e ~ ~ ~ \ ~ ~ ~ ~
CD ~ ~ ~ ~ ~ ~ ~ ~
4 ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~
~ 4 ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ h ~
I~ ~ ~ ~ ~ ~ J ~ ~ ~
~ ~ ~ ~
~
~ ~ ~
~ ~
~ ~ ~ ~ 4
~ 0 ~
~ ~ ~ ~
~ ~ ~ ~ 4
~
~
~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~
I ~ 4 ~
~ ~ ~
4
~ ~ ~
~ ~
~
~ ~ ~ ~ ~ ~
~ ~ I
~
~ ~
~
h ~
~ ~ 4 ~
~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~' ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
CD ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~
~
~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~ ~ ~
~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ 0 ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
I ~ ~
~ ~
~ ~ a ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~ ~ ~ ~ ~ ~ ~ I~ ~ ~
~
~
~ ~
~ ~
~ ~
~
1
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~
~
~ ~ ~ ~
~ ~ ~ ~ ~
~
~
~
~
CV ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
i Ie
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ S ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ 4 ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~
0
~ 4
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
I ~
~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~
~
~
~ ~ ~ ~
4 ~ ~
~
~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ s ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ S ~ ~ ~ ~ ~ h ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ I ~ ~ ~ ~ ~
~ 4 ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ I 4 ~ 4 ~ ~ ~
~ h ~ ~
i II t ~
~ ~ ~ ~ ~ ~ ~ ~ ~
Chr
~ ~
~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
J ~
~ ~ ~
~ ~
~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
I ~
~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
\ ~ ~
~ ~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ a ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ S ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ e ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ a ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~I ~ ~
~
I' ~ ~ ~ ~
4 ~ ~ I ~ ~
~ ~
~
~ ~
~ ~
~ ~ ~ ~
~
~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
4 ~ ~ S ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~
h
~ h
~ ~ ~
S
~ ~
h
~
~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~
I ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ a ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~
~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
I e
I ~ ~ ~
I ~ ~
~ ~ ~
~ ~
~ ~
~
~
~
~
~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ 3 S ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~
~ ~ ~ ~ ~ ~ ~ ~ h ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
I ~ ~ ~ ~
~ ~ ~
~
~ I ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ h ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
Wolfram: Statistical mechanics of cellular automata
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ I ~
~ ~ ~ ~ ~
~ ~
~
I'
~ ~
~
~
~
~
~
' '0
~
~
~
~
~
~ ~
I
~ ~ ~
~
~
~
~
t' ' ~
~
~
~
~ ~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~
~
~ I ~
~ ~ ~
~
~
~
~ ~
~
~
~ ~
~ ~ ~
~ ~
~ ~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
0
~
~
~
~
0 0
~ ~ ~
~
0
~
~
~ 4 0 ~
~
~
~
~ ~
~ ~
~ ~
~
~
4
~
~ ~
~ ~
~
~
~
~
~ ~
~
4
I~
~ 0 ~ ~
~
~
~
4
~
~
~
~
~
~ ~ ~ 0
~ .~ I ~ ~ ~ ~ ~
I ~
~ ~
I ~ ~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
0
~
~
~
~
I~0 ~
'~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N
~
~
~
~
~
~
~
~ ~
I I I~I ~ ~ ~ ~ ~
~ ~
~
~ ~
~ ~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
I~ ~
~ ~
~ ~ ~
~
~
~ ~
~
~
~
~
~ ~
~ ~ ~
~ ~
~
~
~ ~
~ ~
~
~
~
0 I
~ ~ ~
lV
~
~
~
~
~
~
~
~
~ ~
~ ~
~ ~ ~ ~ ~
II~I ~
~ ~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~
~
~ ~ ~
I ' ~ ~ ~
I
lV
0
~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ I ~ ~ ~
~ I~ ~ ~
~
~
~
~
~
~ ~ ~
~
~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
I ~
0
~
I~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
P ~ ~ ~ ~ ~ ~ ~ ~ '
l
~
~
' ~ ~
' ' ~ ~ I '~ ~ ~ I
~ ~ ~ ~
P
N
~ ~ ~
~
~
~
~
~
~
~
~
~
~
~
~
I I ~. ~ ~
~
~ ~
~
~
It
~ ~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~ ~ ~
~
~
' ~
~
~
~
~
~
~
I
IV ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~
~
~
~
~ ~
I I0 ~ ~
I ~ ~
I ~
~ ~
~ ~ ~
~ ~ ~
~
~
~
~ ~
~ ~ ~
~ ~ ~
~ ~ ~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~4
~
~
~
~
~
~ ~
~ I ~ ~ ~ ~
~
~
~
~ ~
~
~
~ ~
~
~ ~
~
~ ~ ~
~
~
~
~ ~ ~
~ ~ ~
~
~
~ ~
~ ~
~ ~
~
~ ~
~ ~ ~ ~ ~ ~ ~ ~
IV ~
~
~
~
~
~
~
~ ~
I
~
~
~
~
~
~
~
~
0
~
~
~
~
~
~
~
~ ~
~
~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~
IV
~ ~
~
~
~
~
~
~ 4
~
I~~~ 0 ~
~
~
I ~
\ ~
~ ~
~ ~
4
~ ~
~
~
~
~
~
~
~
0 ~
~
~
~
~
~ ~
~
~
~
~ ~
~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0
~
~
~
~
~
~
~
~ ~
~
I ~
I~ ~ 0
~
~
~
~ 0
~ ~
~
~
I ~
~ ~ ~ ~ ~ ~
~ ~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~
~
~
~
~ ~
~
~
I
~
~
~
~
~
~ ~
~
~ ~ ~ ~
~
~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~
~ ~
~
~
~
~
~
~
~
~
~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
I~~ ~
~
~
~
~
~
~
~
~ ~
~ ~
~
~
~
~
~
~
~
~
~
~
~ ~
~ ~
~
~ ~
~ ~
~
~
~ ~
~ ~ ~ ~
~ ~
~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
isl
e ~ IS ~ PO ~ tt IA
-Is ~ ~ ss ss----------OIIIICCIICC
~ ~ ~
~ 11 ~ O'4 St ~ ~
Is ~ ps 1 ~ hhISIhhhhhhS
~ hs ~ r 0 ~ 1
~ ~ hh ~ PO ~ ~01
Vh ~ 4' ~ ~ PS % ~
%%%4%4 ~ ~ Ott
4 %1%1
I
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
I I ~ I ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ I I ~ ~ I ~
~ ~ ~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~
~
~
~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~ I ~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ 5' ~ ~ ~ ~
~
~ ~
~ ~
5
~ ~ ~
~ ~ ~
'I ~ ~ ~ ~ ~
~
~
~
~ ~
~ ~
~ ~
~ ~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~
I
~
~ I ~ ~
~ ~
~
~
0
' 'll 't
~ ~
~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~
e
IV
~ ~ 4
~~ ~ ~
~ ~
~ ~
~ 0 .0 ~ ~
~
4
~
~ ~
~
~ ~
~ ~ 515 ~ 0 ~ ~
~ ~
~ ~
0
0
~
4
~ a
~
~ ~
~ ~
~
~ ~
~ ~ ~
~ ~ ~
~ ~
4 ~ ~
~
~ ~
~
~ ~ ~ 4 ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4
~ ~ ~ ~ ~
~ ~
~ ~ ~
~ ~
~ ~
~ ~
~ ~ ~
~ ~
~ ~ ~
~
~
~
~
~
I ~ ~
~ ~
I~
~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~
~
~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
~ ~
~ ~
~ ~ ~
~ ~ ~
~
I I
~ ~ ~ ~
eIV ~ ~ ~ ~ ~ ~ I ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~
~
~ ~ ~
~ ~
~ ~
~ ~
~
~ ~
~
~
~
~ ~ ~
~ ~
4 I ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~ ~
55 ~ ~
~ ~ ~ ~ ~ ~ I ~
~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ 0
~ '
j ~ ~
~ ~ ~ ~
~ ~ ~
~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~
~
I~
~
~
~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~
~ ~
~
~
~
~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
IV
IV
~ ~ ~ ~
~ ~' ~
~ ~
~
~ ~
~ ~
I~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
Il l5~
~ ~ ~
I~ ~
~ ~
~
~ ~
~
~
~ ~
~
~ ~
~
~
~
~
~
~
~
~
~
~ ~
~ ~
~ ~ ~ ~
~
~
~
~
~ ~
N ~ ~ I ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~
)I I~ ~ ~
555 ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~
)~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
~
~
~ ~
~
~
~
~
~
~ ~
~ ~
I I 0
~ ~ ~ ~ ~
eIV ~ ~ ~ ~
~ ~ ~
I ~
~ ~ ~ ~
~
~
~ ~
~ ~ ~ ~
~ ~ ~
I ~ I
~
~ ~ ~ ~
~
~ ~
~
~
~ ~ ~ ~
Its
~ ~
I
~
~ ~
~ ~ ~
~ ~ ~ ~
0'
~ ~
~ ~
~
~ ~
~
~
~ ~
~ ~
Sl ~ ~ ~
~ ~ ~
~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~
I' Il
~ ~
~
~ ~ ~ ~ ~ ~ ~ ~
~
I ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~
I ~ ~ ~
~ ~
~
~
~
~ ~
~ ~
~ ~
~ ~
5
~
~
0
~
~
~ ~
~ ~
4 ~
~
~
~
~ ~
~ ~
~
I
~ ~
I
~
~
~
I ~
~ ~
~ ~
~ ~
~ ~
~ ~
~
~
~
~ ~ ~
~ ~ ~
~ ~
~ ~
~
~ ~
~
~ ~
~ ~
~
~
~ ~ ~
~ ~
~ ~
~ ~
~
~ ~ ~ 4 ~ ~ 00 ~ 4 ~ ~ 0 0 0 ~ ~ ~ ~ ~ ~ ~ ~
N 0 ~ ~ ~
~ ~ 5 ~ ~ t~ ~ ~ ~ I~ ~~ ~~ ~ ~ ~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~
eIV ~ ~
~ ~
~ ~
~ ~
~
~
~ ~
~
~ ~ ~
~
~
~ ~
~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~
~
~ ~
~
~
~ ~ ~
~ ~ ~
~ ~
~ ~
~
~
~ ~
~
~ ~
~ ~
. ~ ~ ~ I~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
~ ~
~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
1 11 ~ 1 ~ 0 ~ ~ ~ 11 ~ tos ~ ~ 111%%4 I
%set ~ ~ t
IICIC 1 %sets ~ ~ ~ ~ %0 ~ Pt ~ ~ 0~ Pe ~ ~ 0
Vh
1%%%%1%%%%4 ~
~ IS ~ 4 4~ ~~~ IS ~ POS ~ t ~11%1'
1114 1st
Pe 1111 ~
~
~ ~ ~ t~ ~p 0 %here I~I ~ sts
v s
~ ~ ~ ~ ~ 4 s ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~
50 ~
' ll
~ ~ ~
~
~
~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~
~ ~ ~ ~
~
~
~ ~ ~ ~
~ ~ ~ ~ ~
~
~ ~
~ ~
~
~ ~
~ ~
~ ~
~ ~
~
~ ~
~
~
~
~ ~
~ ~ ~
~
~ ~ ~ ~
~ ~ ~ ~ ~ 555
~
'
~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ '
~ ~ ~
~
~
~ ~ ~
~ ~
~ ~ ~
~ ~
~ ~
~
~ ~ ~
~
~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~
~
~ ~ ~ ~
~ ~ ~
~
~
~
~
~
~ ~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~
~ ~ ~
~ ~ ~ 'll'
~ ~ ~ ~
~ ~ ~ ~ ~
~
~ ~ ~ ~
~
~
05055
~ ~
~
~ ~ ~ ~ ~ ~
''0''''
~ ~ ~
~
I ~
~
~
~ ~ ~
~ ~
~ ~ ~ ~ ~
I 0055~
~
~
~
~ ~ ~
~
~
~ ~
~ ~
~
~
~
~
~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~
~ ~ ~
~
~ ~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~
~ ~
~
~ ~ ~
~
~ ~
~
~ ~
~
~
~
~ ~ ~
~
~
~ ~
'' ~ ~ ~ ~ ~ I~ ~
~ ~ ~
~ ~ ~
'tt~ ~
~
~ ~ ~
I I I ~
~ ~ ~
~
~
~ ~ ~
~ ~
~ ~
~ ~ ~
I
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ''555
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ts
~ ~
~ ~
~ ~ ~ ~
~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~ 55'
~
~ ~
~ ~
~
I
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
e ~ ~
~ ~
~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~
55~
~ ~ ~ ~
' ~ ~ ' ~I ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~
~
~ ~ ~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~
~ ~ ~ ~
~ ~ ~
~
~ ~
~ ~ ~
~
N ~ ~ 50 ~
' ~ ll ~ ~ ~
~
~ ~
~ ~ ~ ~
I
~ ~
~ ~
~ ~ ~
~ ~
~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~
~
~ ~
~ ~
~ ~
~
~ ~
~ ~
~ ~ ~
~
~ ~ ~
~ ~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~ ~
~
~
~ ~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~
~
IV
0 .
~ ~
~ .
~ ~
IIIII,
050
~ ~
5555 ~ 0 0
0~ ~ ~ 0
~ ~ ~
~ ~
~ ~
~ ~ ~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~ ~
0 ~ 0~
~ ~ ~ ~
~ ~ 0 ~
~ ~
II
~ ~ ~ ~ ~ ~ ~ ~
~ 0 ~ ~ ~
~ ~ ~ ~
~
~
~ ~ ~
~ ~ ~ ~
~ ~ ~ ~
~ ~ ~
~
e ~
0~
~
0 ~ 0~
~ I ~t lt ~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~
~
~
0
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
55 ~~~ 4~~ 0
~ tlat.
~ ~ ~ ~
~
~ 0
~
~ ~
~ ~ ~ ~ ~ ~
'
~
~ ~ ~ ~ ~
~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~
lttl' 'll 4 ~
~ ~
~
~ ~
~ ~ ~ ~
~ ~
~ ~
~ ~ ~
~ ~ ~
0 ~ 4 ~~ ~
~
~ ~
~ ~ ~
~
~
~
~
~
~
~
~
~ ~ I ~ ~ I ~~ ~ ~ ~
~ ~
~ ~
~ I ~
~ ~ ~ ~ ~ ~
~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
It I
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
)jjii
~
~ ~
tltI
IV ~ ~ ~ ~ ~ ~ ~ ~
ji '.'
~
~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
IV ~ ~
~ ~
~
~ ~ ~ ~
I~~ 555' ~ ~ ~
~ 55 ~ ~
~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~
~ ~ ~ ~ ~
~ ~ ~ ~
~
~
~
~
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~
~ ~ ~
~
~
~
~
~
~
~
~
~
F 5
~ 0 ~ ~
~ ~ ~ ~ ~ ~
I 55' 0 ~
~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~
~ ~ ~
I
~ ~
~ ~
I ~
~ ~ ~ ~ ~
~ ~
~ ~ ~
~
~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~
~ ~
~ ~
~ ~ ~
~ ~
~ ~
~ ~ ~
~
~
~
~
~
~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~
~
~
~
~
~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
5
~ ~
~ ~ ~
I
~ ~ ~
~
~
.~ ~ ~
~ ~ . I~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~
~ ~
~ ~
~ ~
~ ~
~
~
~
~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ .~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N
~ ~
jitl ~ ~
~ ~ ~
~
~ ~ ~ ~
~ ~ ~
~ ~ ~ ~
~
' I ~ ~
~ ~
~ ~
I
~ ~
~
I~ ~ ~
~ ~
~ ~ ~
~
~ ~
~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
5 ~ Ill@ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~
~
~
~ ~
~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
eN ~ ~ ~ ~ 555 ~ ~
~ ~
~ ~
~ ~
~ ~
50 ~ ~
~ ~ ~
00505 I
~ ~ ~ ~
~ ~
~
~ ~
~ ~
~ ~ ~ ~
~
~
~
~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~
~
~ ~
~ ~ ~
~ ~ ~
Ilt ~ ~ ~ ~ ~ ~ ~
~
~ ~
al I' ~ ~
~ ~ ~ ~
~ ~ ~
~ ~
~
~ ~
~
~ ~ ~
~
~ ~ ~
~
~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~
~
~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~
~
~
~
~
~ ~ ~
~ ~
~ ~ ~ ~
~ ~
~
~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~
~
~
~
~
~
~
~
~
~ ~ ~
~ ~
~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~ ~
~ ~ ~
~
~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~
~ ~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
lV
lV
~ ~
~ ~ ~ ~
F 055
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~
~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
~ ~ ~
~
~ ~
~ ~ ~
~ ~ ~
~ ~ ~
~ ~
~ ~
~ ~
~
~
~
N ~ ~ le ~
~ ~
~ 0 ~
~ 0 0 ~ ~
Ila ~ ~ ~
~ 0
\ 0
~ a ~
~ ~
0000 ~ ~ ~ ~ ~ ~ ~
~ 0 ~ ~
~ ~ 0
~
~
~ 4 ~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
4 ~ ~ ~ ~ ~ ~ ~ ~ 0
~
~
~ ~
~
~
~ ~ ~
~ ~
~ \ ~
~ ~ ~ ~
~ ~ ~
4 ~
~
~
~
~
~
~ ~ \ ~ ~ ~ ~ ~~ ~ ~ e ~ ~~ ~ ~~ ~~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ I
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Isl
e ~ 11 ~ PS ~ $1 ~ IS ~ ts ~~~ IIOPO ~ ~~ SS
111%1%1%1 ~ IS ~ ~ ~ ~~~
hsep ~I ~ I ~ pt ors
to%11%%%%% ~ II ~ POS ~ 1 ~ 11 ~ so ~ ~ CI I I ICIICC5 ~ hs ~ p ~~ I~I % 4 ~ 4 ~ o to%0 '%%%%1%0
'v ~ 4' ~ st%1
s
~
I ~I~I~ ~ ~ ~ ~ ~ as ~ ~ 0040404 ~ \ ~ ~ ~ ~
I~ t III ~ ~ ~
I ~ I t ~~ I 0~ 0 ~ 0 ~
I~~
~
~
~
~
~ 50 50505 I' ~
I
~ ~ ~ ~
~ ~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
'I ~
~
I ~~ I ~~ ~ ~
~
~
~
~
~
~ ~
~
~
~
~
~
~
~ ~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~
~
~
~ 0 I~ ~ I~I~I
~
~ 50 I
~
~ I
~
~ I ~ I ~
~
~ ~ I~I~~ ~ I te
~
~
~
I
~
~
~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
e ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~
~
~
~
~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~
~ ~
e ~
~ ~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~
5
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~
~
~ ~ ~
~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~
~
I
~
~ ~
~ ~
~ ~
~
~
~
~
~ ~ ~
~
~ ~ ~ ~ ~ ~ 0 ~ I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I
~
0
4
~
~
0
~
~
~
~ ~
~
~ ~ ~
0
~
~
~
~
~
4
~ ~
~
~
4 ~~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~
~ ~
~
~
~
~
~
0 ~ ~ ~~ ~
~
~ '5jtlltl
~ ~ ~ ~ 0~ \ ~
~ ~
~ ~
~
~ ~
~
~
~
~
~
0
4
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~ ~ ~ ~
~ ~
~
0 ~ ~
~
~
~
~
~
~ ~
~
~
~
~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
IV ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
IS ~ ~ ~ ~ ~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~
I~
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
IV ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
lS ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
IV ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
0 ~ ~ ~ 4 ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ 4 ~ 0 ~ ~ ~ ~ ~ ~
lsl
It ~ Is ~ 1 ~ Ot I I 0 1 ~ ss ~IIIIICIIIIP
11 0 ts ~
~ 4
~ IS ~ tto Oh ~ ~ 1st %1 ~ ro st ~ehhhh
~ h ~ pe ~~ 0
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
0 ~ ~ ~
~
~
~
~ ~ ~
~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 4
0 ~ e ~ 0 ~ 0 ~ ~ ~ ~ ~ ~ ~ 0 ~ ~ ~ ~ ~
4 ~~ ~ s ~ ~ ~ 0 ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
I
~ ~ ~ ~ ~
I ~~ ~~ ~
~
~ ~
~
54' 5 ~
~ ~ ~
~ ~ ~
~
~
~
~
~
~
55
~ ~
~ ~ ~ ~ ~
~
~ ~
~ ~
~
~ ~ ~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~
~
~
~
~
~ ~
I' ~
~ ~
~ ~ ~
~ ~
~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~
~ ~
~ ~ 5 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
N ~ ~ ~ )
N ~
~
0 ~
~ ~
~
~ ~ ~ ~ ~
~ ~ ~
~ I~~
~ ~
~ ~
~
~
~ ~
~ ~
''I ~
''555'
I ~
~
~ ~ ~ ~
~
555 ~ ~
~ ~
~ ~
~ ~
~
'
. ~ I'le ~ ~
~ ~ ~ ~ ~
~ ~
~
~
~ ~
~ ~
~ ~ ~
~ ~
~ ~
~ ~
~ ~ ~
~ ~
~ ~ ~
~ ~ ~ ~
~
~
IV 0 ~ 0 ~ ~ ~ ~ ~ ~ ~ ~
0 ~ I ~ ~ 0 ~
0
~
~ ~ ~
~ ~ ~ ~ ~
0 4 ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~
I
II
~ ~ ~ ~
0 ~ ~ ~ ~ ~ ~ ~
~ ~ ~ I ~ ~ ~ ~
~
~ ~
~
~ ~
~4 ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
N I ~ ~ ~ ~ ~ ~ ~ ~ I I~ ~ ~ ~
~ ~
e
IV ~
~
4 ~
~
~
I
~
~ ~
~ ~
~
~ ~ ~
~ ~ ~ ~ ~
~ ~ ~ ~
I ~~ ~~ ~
~
~ ~ ~
~ ~
~ ~ ~
I~ ~ I~ ~ ~ ~
~ ~
~
~
~
~ ~ ees
N
~
~
~
~
~
~
ll
~ ~ ~ ~
~ ~ ~
~ ~
55~ ~
I
~
~
~
~
~
~
~ ~
~ ~
~
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
lsl
1st%%%%%%%%%%
V
e ~ "%sess ~ ss CIIIOCCLCCC ~ '4 ~ ~ 0' ~ ~ t~ I epe ~ ~ to I III
1% I I I I Iots
~ to ~ ~ I I ~ 1 ~ 0 ~ ~ 1 Iseto ~ Isetos
opsI 11I II Ihhops
IC ~ %1 ~ P ~ i'Ot ~ %Pcs 4 4 ~4 % ~ ~ ~
CO
Gh
cg
C4)
oO
II II I I I O
I I I I
II I G
4
II I Ilt I II o
I I I I
II I I II I I ~ 'o
4 I I II I o
II I I I I I II II I1 4 II 4 a5
II I I I I 4
I n.
I I II II I I I I
II
I 4 I
II I I I
I I tl III I
I II
II I I I III I 4 I
I I I II I I II I G. o
I
I II II I II II II I I II
L
1 II II II II I I QJ
I I I II I
k
E o
II ~I I I
I I I I II II II I II I II I It
I I I
&LP
c5
O
I II I
I I II I II oa
4
I I I
G
I I I ed a5
4 I I
4
II II I I I I III I II~ I II I I~ I II oo
I I I I I ~ ~
1
lf
II I III I
o
I I II I II ~
I I
4
I 1
P
I II I
~ o.&
V
P
I I I I I I II I I I I II
IS
I I
I
C6
C5
ca
I
4 o
I I I II I 4
II tt
II I ~
~t I 1
I
aII I I II
I I ~ I
I 4
I
I o
~ 4
II
II I o
4 I 1
I II III I1 4I 4
~ I
1
1 I 4 a5
4
~ — ri
g5
(
P
I
4
II O
I tt
c5
II a5
II I II III I 1I I I II I II 1
4 I
I I I I I I I ~ II I I I I
II I II I II 1 II I II 1 II I I I I I I 1 I
I I I II I I If Ilt I I II I II I II k
I 2
g -~ Q
4 I oC
I oO
~ 1 P V
III III II1I II 1II III I I «A C5
4 I I I I 4 I I I I I I I 1 I I ~
I
o cA
P
I4 II I I 4I k CJ
I I 1 I 4
~ I
1
I 1 I I o
~ I1I I I I o~ ~
oo
~ c5
~ I
o
+4 1 m«ft S ~ Al ttt V Vl Be m It af
$~NPt%04f m
m~emveer me af
~ ~ ~ ~
«o
o
a5
)
and its nearest neighbors. However, in d 1 dimensions
two possible identifications of nearest neighbors can be
A particular type-II two-dimensional cellular automa-
ton whose evolution has been studied extensively is the
made. First, sites may be considered neighbors if one of game of "Life" (Conway, 1970; Gardner, 1971, 1972;
their coordinates differ by one unit, and all others are Wainwright, 1971—1973; Wainwright, 1974; Bucking-
equal, so that the sites are "orthogonally" adjacent. In ham, 1978; Berlekamp et al. , 1982, Chap. 25; R. W.
this case, a "type-I" cellular automaton neighborhood Gosper, private communications). The local rules take a
containing 2d+1 sites is obtained. Second, sites may be site to "die" (attain value zero) unless two or three of its
considered neighbors if none of their coordinates differ by neighbors are "alive" (have value one). If two neighbors
more than one unit, so that the sites are "orthogonally" or are alive, the value of the site is left unchanged; if three
"diagonally" adjacent. This case yields a "type-II" cellu- are alive, the site always takes on the value one. Many
lar automaton neighborhood containing 3" sites. When configurations exhibiting particular properties have been
d =1, type-I and -II neighborhoods are identical and each found. The simplest isolated configurations invariant
contains three sites. For d =2, the type-I neighborhood under time evolution are the "square" (or "block" ) con-
contains five sites, while the type-II neighborhood con- sisting of four adjacent live sites, and the "hexagon" (or
tains nine sites. ' Cellular automaton rules may be con- "beehive") containing six live sites. "Oscillator" configu-
sidered legal if they satisfy the quiescence condition and rations which cycle through a sequence of states are also
are invariant under the rotation and reflection symmetries known. The simplest is the "blinker" consisting of a line
of the lattice. For d=2, the number of possible legal of three live sites, which cycles with a period of two time
k'" +" + " ',
type-I rules with k states per site is found to be
yielding 2"=2048 rules for k=2 and
3 '=8)&10 for k =3. The number of type-II rules with
steps. Oscillators with periods 3, 5, and 7 are also known;
other periods may be obtained by composition. So long as
they are separated by four or more unfilled sites, many of
k = 2 in two dimensions is found to be 2 =6 X 10' (or these structures may exist without interference in the con-
2 ' if reflection symmetries are not imposed). figuration of a cellular automaton, and their effects are
Figure 32 shows the evolution of an initial configura- localized. There also exist configurations which "move"
tion containing a single nonzero site according to two- uniformly across the lattice, executing a cycle of a few
dimensional (type-I) modulo-two rules. In case (a) the internal states. The simplest example is the "glider"
value of a site is taken to be the sum modulo two of the which contains five live sites and undergoes a cycle of
values of its four neighbors on the previous time step, in length two. The number of filled sites in all the configu-
analogy with one-dimensional cellular automaton rule 90. rations mentioned so far is bounded as a function of time.
In case (b), the previous value of the site itself included in However, "glider gun" configurations have been found
the sum (and the complement is taken}, in analogy with which generate infinite streams of gliders, yielding a con-
rule 150. The sequence of patterns obtained at successive tinually increasing number of live sites. The simplest
time steps may be "stacked" to form pyramidal structures known glider gun configuration evolves from a configura-
in three-dimensional space. These structures become tion containing 26 live cells. Monte Carlo simulation sug-
self-similar at large times: in case (a) they exhibit a fractal gests that a disordered state of X cells usually evolves to
dimension log&5=2. 32, and in case (b) a dimension a steady state within about 1V time steps (and typically
7
I+logi(1+i/3)=2. 45. The patterns found on vertical an order of magnitude quicker); very few of the 2 possi-
slices containing the original nonzero site through the py- ble configurations are visited. Complicated structures
ramids (along one of the two lattice directions) are the such as glider guns are very rarely produced. Rough em-
same as those generated by the one-dimensional modulo- pirical investigation suggests that the density of structures
two rules discussed in Secs. II and III. The patterns ob- containing L live sites generated from a disordered initial
—L
tained at each time step in Fig. 31 are almost always self- state (cf. Buckingham, 1981} decreases like e /I. ,
similar in the large time limit. For case (a), the number where L is the size of the minimal distinct configura-
31 is found to be 4,
of sites with value one generated after ~ time steps in Fig.
¹)«& where
pi(r ) gives the number of
occurrences of the digit one in the binary decomposition
tion which evolves to the required structure in one time
step. Just as for the one-dimensional cellular automata
discussed in Sec. IV, the irreversibility of "Life" leads to
of the integer ~, as discussed in Sec. III (cf. Butler and configurations which cannot be reached by evolution
Ntafos, 1977). The type-I modulo-two rules may be gen- from any other configurations, and can appear only as in-
eralized to d-dimensional cellular automata. In case (a} itial states. However, the simplest known "unreachable"
the patterns obtained by evolution from a single nonzero configuration contains around 300 sites (Wainwright,
initial site have fractal dimension log&(2d+1) and give 1971— 1973; Hardouin-Duparc, 1974; Berlekamp et al. ,
(2d) ' nonzero sites at time step r. In case (b), the 1982, Chap. 25).
asymptotic fractal dimension is found to be The game of "Life" is an example of a special class of
log2[d(&1+4/d + 1)]. Once again, simple initial states "totalistic" cellular automata, in which the value of a site
always yield self-similar structures in the large time limit. depends only on the sum of the values of its neighbors at
the previous time step, and not on their individual values.
Such cellular automata may arise as models of systems in-
In the case d =2, neighborhoods of types I and II are known volving additive local quantities, such as chemical con-
as von Neumann and Moore neighborhoods, respectively. centrations. In one dimension with k =2 (and three sites
bO
~ 04I
Pl
ch 0
~ ! ~ ~ ~
0
I cl
O
~ ~ ~ ~ 5
~ ~ ~
~ ls ~ ~
~ ~
~ ~ 0 ~
~ ~ ~
~
0
0 4
~ ~ ~
0 ~ ~
0
~ ~ ~
0 ~
~
~
~
~
\ 4
0
~ ~
~
4
0 ~
0
0 0 0~ 0 40
g
0
~
0 00 0 0 ~ ~ 4
~
~
~ ~
~~
~
4~
~ ~ ~ 00
0 0
e0
~ ~ ~ ~
0 ~
~
0 ~
~
04
0
~ ~ ~ ~ 0 ~
~ ~
0
~
~ ~ ~ ~ ~
~ 0 ~
~ ~ ~ ~
'0
0 ~0 ~ ~
g
~
I~ ~ t ~ 0 ~ 4
~
C ~
~
~ ~ 0 0 ~
4 ~
4
~ 4 ~
~ ~ ~ ~ 0~ ~ ~ ~ ~ ~ 4 ~ '~ ~
~ ~
0
0 ~ ~
~ ~ ~
~
~
~
e ~ ~
~
~
~
4 0 ~ CL p5
~ 044
~ ~ ~
~ ~ ~ ~ ~ 4 ~ ~ ~ ~ ~ ~ ~
0 CP
~
~ ~ ~ ~ 4
~ ~
~
~ ~ ~ ~ ~ ~ ~~ ch
~ ~
4 ~ ~ ~
~
~ ~
4
0 ~ ~
~ ~ ~
~ ~
.g of
~ ~
cd
Q 0~
~ ~ ~ o e
««f
~ ~ ~ ~ ~ ~ ~
~ ~ ~ 0
~ ~
~ ~ ~ 0 ~ ~
0 ~
~ ~ ~ ~ ~ ~ 0 ~ 0
0 ~
~ ~ ~ ch
2.0-
~ ~ 4
~ ~
r 0 ~ ~ ~ 0
C
~ ~
~ ~ ~ CJ 0
CJ ™
«cf
g 6ch 00%4
~ ~ ~
~ 0 ~
~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~
0 ch
.+~
~ ~ ~
~ ~ 0 0 ~ ~ ~
~ ~ ~ ~ 0 ~ 0 ~
0
g
~ 0 0 ~ 0 ~ ~ 0 ~ ~ 0 ~ ~ r ~ e ~ ~ ~ I
«d C4
~ ~ 0 ~ ~ ~
0 0 4
~ ~
~ 0 0 ~ ~ ~ Q. C
0
~
~ ~ ~ ~ ~ ~ ~ ~ ~
gp ch
~ ~ ~ ~ ~
C7
Q
Ch
QJ
«cf
ch
4k
ch
0 g cd
«d
ch ch
0 0
~ ~
C) ««5 V 4P
y5
«cf cd
~
0
IrrI
Yp
O cj
g4
a ~ 43
0 0
bQ ~ ~
~
~
~
~
~
~
~
~ ~ O O M
0 ~ ~ 0
~i
~ ~ ~ ~ ~
~
~
~
~
~
~
~ ~ ~
~
~
~
~
~ ~
~
~
~
~
«d
~ ~
~ ~ ~ ~ ~ ~
~ ~ ~ ~
\ ~ 0 ~ ~
0 C
~
~
~
0
~
~
~
~
~
~
~
~
~
~
~
0 ~
~
0
0
~
~
~
~
~
~
~
~
~
0
~
~
~
~
~
~
~ ~
~
~
~
~
~
~
~
~
~
~ ~ ~
~
~
~ ~
~
~
0
~
~
~
~
~
~
~
~
~
~
~
~
~
0
4
~
~
~
~
~
~
~ ~
~
~
~
~
~ ~
~
~
~
0
~
~
~
\
~
~
a «d ch
0 0 ~ 0 ~ ~ ~
~ ~ ~ ~ 0 ~ ~ ~ ~ 0
~ 4 4 ~ 4 ~ 0 4 ~ e 0 ~ ~ 4
~ 0
~ ~ ~ ~ 4
~ ~
0 ~ e
0
~ ~ ~ ~ «d
0 ~ ~ ~ ~
~
~
~
~
C
~
~
~
~
~
~
~
~
~ ~
~
~ ~
~
~
~
~
~
~
~
~
~
~
~
~
~ ~ ~ m
ch
g$
0 ch
0
~ ~
~ ~ ~
0
Cf
V 0 o
0 &
tg
0
bQ OP
0 ~ A
Ch «d
ch
0
«0
ch
~ ~
OJ
~ ~
cD 0 «5
4J
ch
cd
gv «cf
Q
ch
~ ~ gp
~
«cf
~ ~ ~
~
0
~ ~ ~ ~ 0 ~ ~ 0
~ 0 ~ ~ ~ ~
~
0
~ ~ ~
~
0
~
~ ~ ~ ~ 0 ch
E
g$
~ ~ ~ ~ 0 ~ 000
~ ~ ~ ~
0 ~
~ ~ 0 0 0
0 0 Q
E~
~ ~
~ 0WI CP
~ ~
47
p 60 ~
OP
O
Q Q
ccf
0
g
O CO
C
E. ~
o
cc
in each neighborhood) all cellular automaton rules are to- encoded. Many Turing machines have been shown to be
talistic. In general, the number of totalistic (legal) sets of computationally universal. The simplest has seven inter-
rules for cellular automata with v neighbors for each site nal states, and allows four possible "symbols" in each
is k( ')'" +".
In one dimension with k=3, =5&&10 of square of its tape. One method for demonstrating compu-
the =10 possible rules are therefore totalistic. Only 243 tational universality of cellular automata shows
of the totalistic rules are also periperal in the sense de- correspondence with a universal Turing machine. The
fined in Sec. II. With k=2 in two dimensions, 2 of the head of the Turing machine is typically represented by a
2" possible rules in a type-I neighborhood are totalistic phononlike structure which propagates along the cellular
(and 32 are also peripheral), and 2"
of the 2 in a type-II automaton. It may be shown (Smith, 1971) that an
neighborhood. eighteen-state one-dimensional cellular automaton with a
A potentially important feature of cellular automata is three-site neighborhood can simulate the seven-state
the capability for "self-reproduction" through which the four-symbol Turing machine in this way, and is therefore
evolution of a configuration yields several separated iden- computationally uni versal. Simpler computationally
tical copies of the configuration. Figure 33 illustrates a universal cellular automata must be found by other
very simple form of self-reproduction with the elementary methods. The most straightforward method is to show
one-dimensional modulo-two rule (see Waksman, 1969; correspondence with a standard digital computer or elec-
Amoroso and Cooper, 1971; Fredkin, 1981). With a sin- tronic circuit by identifying cellular automaton structures
gle nonzero site in the initial state, a configuration con-
"
which act like "wires, carrying signals without dissipa-
taining exactly two nonzero sites is obtained after 21 time tion and crossing without interference, and structures
steps' as indicated by Eq. (3.2). The additive superposi- representing NANO gates at intersections between wires.
tion property of the modulo-two rule implies that results "Memories" which maintain the same state for all time
for more complicated initial states are obtained by super- are also required. In the Life-game cellular automaton
position of those for single-site initial states. Thus after discussed above, streams of gliders generated by glider
7 = 2 time steps, for sufficiently large j, the cellular au- guns may be used as wires, with bits in the signal
tornaton generates two exact copies of any initial sequence represented by the presence or absence of gliders. At the
of site values. After a further 21 ' time steps, four copies points where "glider streams" meet, other structures
are obtained. However, after another 2J ' time steps, the determine whether the corresponding wires cross or in-
innermost pair of these copies meet again, and annihilate, "
teract through a "NANO gate. The Life-garne cellular au-
leaving only two copies when ~=2J+'. Purely geometri- tornaton is thus computationally universal. "Circuits"
cal "overcrowding" thus prevents exponential multiplica- such as binary adders (Buckingham, 1978) may be con-
tion of copies by self-reproduction in this case. An exact- structed from Life configurations. It appears that such
ly analogous phenomenon occurs with the two- circuits run at a speed slower than the digital computers
dimensional rnodulo-two rule illustrated in Fig. 32, and to which they correspond only by a constant multiplica-
its higher-dimensional analogs. In general, the number of tive factor. The "Life game" is a type-II two-dimensional
sites in a d-dimensional cellular automaton configuration cellular automaton with two states per site. A computa-
grows with time at most as fast as (2r ), '
which is asymp- tionally universal type-I two-dimensional cellular automa-
totically slower than the number & (21) required for an ton has been constructed with three states per site (Banks,
exponentially increasing number of copies to be generated. 1971); only two states are required if the initial configura-
Exponential self-reproduction can thus occur only if the tion is permitted to contain an infinite "background" of
copies generated are not precisely identical, but exhibit nonzero sites (Toffoli, 1977a). In one dimension, with a
variability, and for example execute a random walk neighborhood of three sites, there are some preliminary
motion in response to external noise or contain a indications that a universal cellular automaton may be
"counter" which causes later generations to "live" longer constructed with five states per site. The details and im-
before reproducing. plications of this cellular automaton will be described in a
Section IV mentioned the view of cellular automata as future publication.
computers. An important class of computers is those
with the property of "computational universality, for " VI. DISCUSSION
which changes in input alone allow any "computable This paper represents a first step in the investigation of
function" to be evaluated, without any change in internal cellular automata as mathematical models for self-
construction. Universal computers can simulate the organizing statistical systems. The bulk of the paper con-
operation of any other computer if their i~put is suitably sisted in a detailed analysis of elementary cellular automa-
ta involving a sequence of sites on a line, with a binary
" An analogous result holds for all modulo-k rules with k variable at each site evolving in discrete time steps ac-
prime by virtue of the relation (; ) mod k = 0, 0&i &k ~alid cording to the values of its nearest neighbors. Despite the
for all primes k. The relation is a special case of the general re- simplicity of their construction, these systems were found
sult (Knuth, 1973, Sec. 1.2.6, Ex. 10) to exhibit very complicated behavior.
The 32 possible (legal) elementary cellular automata
j [j/kJ j mod k were found to fall into two broad classes. The first class
i [i/kJ i mod k consisted of simple cellular automata whose time evolu-
I
~ M
tA
0
E -" C
aS
0
aS
0
QJ
G4 o
o+ '4
0
P
I
OG
n.
aS
hQ
&
2
o
aS
0
aS
0E
G
aS
aS
o
0
0 0
0
0
E
0
bQ
~
g 0 O
Eom
aS
~ ~ E
ch
aS
0
C
0 V
0~ ~~ ~0
0
~ Pl W & t
CU lP ~ N P) % IA Q) i 6)
LA lP Sl
IQl vwmmmmmmmmmbJbJNNNNCVNNOJP)
aS
aO 0
tion led eventually to simple, usually homogeneous, final for particular configurations, thereby reducing entropy.
states. The second class contained complex cellular auto- This phenomenon allows for the possibility of self-
mata capable of generating quite complicated structures organization by enhancing the probabilities of organized
even from simple initial states. Figure 3 showed the pat- configurations and suppressing disorganized configura-
terns of growth obtained with the very simplest initial tions.
state in which only one site had a nonzero value. The Many of the qualitative features found for elementary
complex rules were found to yield self-similar fractal pat- cellular automata appear to survive in more complicated
terns. For all but one of the rules, the patterns exhibited cellular automata (considered briefly in Sec. V), although
the same fractal dimension log23=1. 59 (the remaining several novel phenomena may appear. For example, in
rule gave a fractal dimension log22y=1. 69). With more one-dimensional cellular automata with three or more
coinplicated initial states, the patterns obtained after evo- possible values at each site, protective membranes may be
lution for many tiine steps remained self-siinilar —
at least generated which shield finite regions from the effects of
on scales larger than the region of nonzero initial sites. external noise, and allow very regular patterns to grow
The generation of self-similar patterns was thus found to from small seeds.
be a generic feature of complex cellular automata evolv- Cellular automata may be viewed as computers, with
ing from simple initial states. This result may provide initial configurations considered as input programs and
some explanation for the widespread occurrence of self- data processed by cellular automaton time evolution. Suf-
similarity in natural systems. ficiently complicated cellular automata are known to be
Section III discussed the evolution of cellular automata universal computers, capable of computing any comput-
from general initial states, in which a finite fraction of able function given appropriate input. Such cellular auto-
the infinite nuinber of initial sites carried value one. Re- mata may be considered as capable of the most complicat-
gardless of the initial density of nonzero sites, definite ed behavior conceivable and are presumably capable of
densities were found in the large time limit. Markovian simulating any physical system given a suitable input en-
master equation approximations to the density develop- coding and a sufficiently long running time. In addition,
ment were found inadequate because of the importance of they may be used to simulate the evolution of any other
"feedback" in the cellular automaton evolution. Even cellular automaton. If the necessary encoding is suffi-
with disordered or random initial states, in which the ciently simple, the statistical properties of the simulated
values of different sites are statistically uncorrelated, the cellular automaton should follow those of the universal
evolution of complex cellular automata was found to lead cellular automaton. Although not capable of universal
to the formation of definite structures, as suggested by simulation, simpler cellular automata may often simulate
Figs. 8 and 15. One characteristic of this self- each other. This capability may well form a basis for the
organization was the generation of long sequences of universality found in the statistical properties of various
correlated sites. The spectrum of these sequences was cellular automata.
found to reach an equilibrium form after only a few time Cellular automata have been developed in this paper as
steps, extending to arbitrarily large scales, but with an ex- general mathematical models. One may anticipate their
ponential damping. The exponents were again found to application as simple models for a wide variety of natural
be universal for all initial states and almost all complex processes. Their nontrivial features are typically evident
cellular automata (with the exception of two special addi- only when some form of growth inhibition is present. Ex-
tive cellular automata). amples are found in aggregation processes in which aggre-
Any initial cellular automaton state was found to lead gation at a particular point prevents further aggregation
at large tiines to configurations with the same statistical at the same point on the next time step.
structures. However, in complex cellular automata, the
trajectories of almost all specific nearby initial configura-
tions (differing by changes in the values at a few sites)
ACKNOWLEDGMENTS
were found to diverge exponentially with time in the
phase space of possible configurations. After a few time
steps, the mapping from initial to final configurations be- I am grateful for suggestions and assistance from J.
comes apparently random (although there are quantitative Ambjorn, N. Margolus, Q. Martin, A. Odlyzko, and T.
deviations from a uniform random mapping). Cellular Shaw, and for discussions with J. Avron, C. Bennett, G.
automaton rules may map several initial configurations Chaitin, J. D. Farmer, R. Feynman, E. Fredkin, M. Gell-
into the same final configuration, and thus lead to micro- Mann, R. W. Gosper, A. Hoogland, T. Toffoli, and W.
scopically irreversible time evolution in which trajectories Zurek. I thank S. Kauffman, R. Landauer, P. Leyland,
of different states may merge. In the limit of an infinite B. Mandelbrot, and A. Norman for suggesting references.
number of sites, a negligible fraction of all the possible The symbolic manipulation computer language SMP
cellular autoinaton configurations are reached by evolu- (Wolfram et al. , 1981) was used in some of the calcula-
tion from any of the possible initial states after a few time tions. Some of this work was done before I resigned from
steps. Starting even from an enseinble in which each pos- Caltech; computer calculations performed at Caltech were
sible configuration appears with equal probability, the cel- supported in part by the U. S. Department of Energy
lular automaton evolution concentrates the probabilities under Contract Number DE-AC-03-8 I-ER40050.
"
dimensional real-time iterative array, J. ACM 12, 388.
REFERENCES
Flanigan, L. K., 1965, "An experimental study of electrical con-
"
duction in the mammalian atrioventricular node, Ph. D. thesis-
Abelson, H. and A. A. diSessa, 1981, Turtle Geometry: The (University of Michigan).
Computer as a Medium for Exp/oring Mathematics (MIT Fredkin, E., 1981, unpubhshed, and PERQ computer demon-
Press, Cambridge). stration (Three Rivers Computer Corp. ).
Aggarwal, S., 1973, "Local and global Garden of Eden Gach, P., G. L. Kurdyumov, and L. A. Levin, 1978, "On@-
"
theorems, University of Michigan technical report No. 147. dimensional uniform arrays that wash out finite islands, "
Aladyev, V., 1974, "Survey of research in the theory of homo- Probl. Peredachi. Info. , 14, 92.
geneous structures and their applications, "
Math. Biosci. 22, Gardner, M. , 1971, "Mathematical Games, '* Sci. Amer. 224,
121. February, 112; March, 106; April, 114.
Aladyev, V., 1976, "The Behavioural Properties of Homogene-
"
Gardner, M. , 1972, "Mathematical Games, Sci. Amer. 226,
"
ous Structures, Math. Biosci. 29, 99. January, 104.
Alekseev, V. M. , and M. V. Yakobson, 1981, "Symbolic dynam- Geffen, Y., A. Aharony, B. B. Mandelbrot, and S. Kirkpatrick,
"
ics and hyperbolic dynamic systems, Phys. Rep. 75, 287. "Solvable fractal family, and its possible relation to the back-
Amoroso, S. and G. Cooper, 1971, "Tessellation structures of
"
bone at percolation, Phys. Rev. Lett. 47, 1771.
reproduction of arbitrary patterns,
"
J. Comput Syst. Sci. 5, Gerola, H. and P. Seiden, 1978, "Stochastic star formation and
455.
"
spiral structure of galaxies, Astrophys. J. 223, 129.
Apostol, T. M. , 1976, Introduction to Analytic Number Theory Glaisher, J. %'. L., 1899, "On the residue of a binomial-theorem
{Springer, Berlin). coefficient with respect to a prime modulus, " Q. J. Math. 30,
ApSimon, H. G., 1970a, "Periodic forests whose largest clear- 150.
"
ings are of size 3, Philos. Trans. R. Soc. London, Ser. A 266, Grolomb, S. W. , 1967, Shift Register Sequences (Holden Day, -
113. San Francisco).
ApSimon, H. G., 1970b, "Periodic forests whose largest clear- Grassberger, P., 1982, "A new mechanism for deterministic dif-
"
ings are of size n & 4, Proc. R. Soc. London, Ser. A 319, 399.
ticlee "
fusion, Wuppertal preprint WU B 82-18.
Arbib, M. A, 1969, Theories of Abstract Automata (Prentice- Greenberg, J. M. , B. D. Hassard, and S. P. Hastings, 1978,
Hall, Englewood Cliffs). "Pattern formation and periodic structures in systems
Atrubin, A. J., 1965, "A one-dimensional real-time iterative modelled by reaction-diffusion "
equations, Bull. Am. Math.
multiplier, " IEEE Trans. Comput. EC-14, 394. Soc. 84, 1296.
Baer, R. M. , and H. M. Martinez, 1974, "Automata and biolo- Griffeath, D., 1970, Additiue and Cancellatiue Interacting Par-
"
gy, Ann. Rev. Biophys. 3, 255. Systems (Springer, Berlin).
Banks, E. R., 1971, "Information processing and transmission Haken, H. , 1975, "Cooperative phenomena in systems far from
in cellular automata, "
MIT Project MAC report No. TR-81. thermal equilibrium and in nonphysical systems, " Rev. Mod.
Barricelli, N. A. , 1972, "Numerical testing of evolution Phys. 47, 67.
"
theories, J. Statist. Comput. Simul. 1, 97. Haken, H. , 1978, Synergetics, 2nd ed. (Springer, Berlin).
Berlekamp, E. R., 1968, Algebraic Coding Theory (McGraw- Haken, H. , 1979, Pattern Formation by Dynamic Systems and
Hill, New York). Pattern Recognition (Springer, Berlin).
Berlekamp, E. R., J. H. Conway, and R. K. Guy, 1982, 8'in- Haken, H. , 1981, Chaos and Order in Nature (Springer, Berlin),
ning Ways for Four Mathematical Plays (Academic, New Hardouin-Duparc, J., 1974, "Paradis terrestre dans l'automate
York), Vol. 2, Chap. 25.
"
cellulaire de conway, R.A. I.R.O. 8 R-3, 63.
"
Buckingham, D. J., 1978, "Some facts of life, Byte 3, 54. Hardy, G. H, and E. M. Wright, 1979, An Introduction to the
Burks, A. %'., 1970, Essays on Cellular Automata (University of Theory of Numbers, 5th ed. (Oxford University Press, Oxford).
Illinois, Urbana). Harris, B., 1960, "Probability distributions related to random
Burks, A. %'., 1973, "Cellular Automata and Natural Systems, " mappings,
"
Ann. Math. Stat. 31, 1045.
Proceedings of the 5th Congress of the Deutsche Gessellschaft Harvey, J. A. , E. %'. Kolb, and S. Wolfram, 1982, unpubhshed.
fur Kybernetik, Nuremberg. Herman, G. T., 1969, "Computing ability of a developmental
Butler, J. T., and S. C. Ntafos, 1977, "The vector string descrip- model for filamentous organisms, " J. Theor. Biol. 25, 421.
tor as a tool in the analysis of cellular automata systems, " Honsberger, R., 1976, "Three surprises from combinatorics and
Math. Biosci. 35, 55. number theory, " in Mathematical Gems II, Dolciani Math.
Codd, E. F., 1968, Cellular Automata (Academic, New York). Expositions (Mathematical Association of America, Oberlin),
Cole, S. N. , 1969, "Real-time computation by n-dimensional p. l.
iterative arrays of finite-state machines, "
IEEE Trans. Com- Hoogland, A. , et al. , 1982, "A special-purpose processor for the
put. C-18, 349.
"
Monte Carlo simulation of Ising spin systems, Delft preprint.
Conway, J. H. , 1970, unpublished. Hopcroft, J. E., and J. D. Ullman, 1979, Introduction to Auto-
Deutsch, E. S., 1972, "Thinning algorithms on rectangular, hex- mata Theory, Languages and Computation (Addison-Wesley,
"
agonal and triangular arrays, Commun. ACM 15, 827. Reading).
Farmer, J. D.„1982a, "Dimension, fractal measures, and chaot- Kauffman, S. A. , 1969, "Metabolic stability and epigenesis in
ic dynamics, "
in Evolution of Order and Chaos in Physics,
"
randomly constructed genetic nets, J. Theor. Biol. 22, 437.
Chemistry and Biology, edited by H. Haken (Springer, Berlin).
"
Kimball, S. H. , et al. , 1958, "Odd binomial coefficients, Am.
Farmer, J. D., 1982b, "Information dimension and the proba- Math. Mon. 65, 368.
"
bilistic structure of chaos, Z. Naturforsch. 37a, 1304. Kitagawa, T., 1974, "Cell space approaches in biomathemat-
Fine, N. J., 1947, "Binomial coefficients modulo a prime, Am.
" "
ics, Math. Biosci. 19, 27.
Math. Mon. 54, 589. Knuth, D. E., 1973, Fundamental Algorithms (Addison-Wesley,
Fischer, P. C., 1965, "Generation of primes by a one- Reading).
Witten, T. A. and L. M. Sander, 1981, "Diffusion-limited ag- organizing systems," Caltech preprint CALT-68-938 (submit-
gregation, a kinetic critical phenomenon, "
Phys. Rev. Lett. 47, ted to Nature).
1400. "
Wolfram, S., 1982b, "Cieometry of binomial coefficients, to be
Wolfram, S., et al. , 1981, "SMP Handbook, " Caltech. published in Am. Math. Monthly.
Wolfram, S., 1982a, "Cellular automata as simple self-
When complex cellular automata evolve from disordered initial states, such as random noise, they typically deform into ordered structures characterized by self-similarity. Throughout this process, regardless of initial state density, all possible complex automata rules yield consistent pattern formations at large timescales, driven by dominant triangle density functions characteristic of non-additive dynamics . This transformation demonstrates cellular automata's capacity to inherently order chaos through repeated local rule application, highlighting their organizational power .
Pattern growth in cellular automata achieves self-similarity through local processes involving repeated interactions and transformations following set rules. These local processes cycle through deterministic steps that magnify initial differences into complex, fractally self-similar structures. The resultant patterns display a characteristic scale-invariance across growth stages, capturing the intrinsic rule-based symmetry in evolving local interactions, marking the cellular automaton's potential for emulating universal natural patterns . This reflection is paramount in emphasizing rule significance in the emergence of complex behaviors from simple algorithmic origins .
Cellular automata rules are foundational in developing universal structures due to their ability to simulate processes leading to self-similarity in varied systems. These rules generate pattern evolution standardized by distinctive statistical properties, predictive despite varying initial configurations. The underlying local interactions prescribed by such rules create self-similar structures by iterating fundamental processes that naturally produce universal fractal patterns . This mechanism suggests a general principle applicable across many complex systems sharing local cellular automata-like dynamics .
Additive cellular automata rules, like rules 90 and 150, display a distinct behavior in generating triangle densities compared to non-additive rules. These additive rules result in a lower density of triangles that follow an exponential decay, contrasting with non-additive rules like rules 18, 22, and 126, which populate higher density curves and generally produce more extensive pattern variations over time . The fundamental difference lies in the nature of pattern superposition and triangle generation tendencies .
Modulo-k rules in cellular automata dictate site value configurations by cycling values through predefined state limits based on nearest-neighbor sums. The influence of these rules results in a predictable pattern across sites with periodicity dependent on k, establishing structured sequences that often adhere to modular arithmetic principles . This principle underpins the movement and transformation of patterns and applies universally across configurations derived from single initial sites, demonstrating the consistent and repeatable nature of pseudo-random evolutions fostered by modulo-k constraints .
Self-organization in cellular automata manifests as triangular patterns appearing over time, particularly visible through fluctuations resulting from sequence consistency in site values. These patterns start with a sequence of sites sharing the same value, progressively reducing until reaching a triangle's apex, which qualitatively identifies self-organization . The quantitative confirmation of this phenomenon is demonstrated through the equilibrium states reached after extensive evolution regardless of initial configuration, showcasing self-organized order from random initial states .
Cellular automata demonstrate universality in statistical properties by exhibiting consistent behaviors and pattern formations across different rules yet sharing similar statistical frameworks. This universality is demonstrated by encoding an initial configuration under one rule to emulate another's pattern evolution, ensuring statistical consistency across diverse setups . Such representability highlights the foundational commonalities driving complex automata despite surface differences, with shared statistical traits providing a unified understanding of emergent behaviors across distinct rules .
In cellular automata, initial configurations significantly influence pattern evolution. Specifically, the initial configuration under rule 90 determines the appearance and number of triangles, as indicated by a pattern that becomes a superposition of those generated from each initial nonzero site . This pattern evolution, involving self-similarity and fractal dimensions, depends on this superposition and results in triangles of various sizes emerging as the automaton evolves .
The fractal dimension in cellular automata serves as a measure for the complexity and self-similarity of emergent patterns. These patterns, especially under certain rules, exhibit structures that are self-repeating across scales. The fractal dimension, often expressed in terms of log ratios, quantifies this self-similarity by defining how pattern complexity evolves with scale changes . It's generally characterized as a constant or predictable number for particular cellular automata, reflecting the intrinsic scale of initial states and subsequent pattern growth .
The superposition property of cellular automaton patterns signifies that the overall pattern formation from any arbitrary initial state is essentially a composite of patterns initiated from each active site independently. This property implies a linear response to initial configurations, pivotal for understanding pattern dynamics in rule-based systems and establishes that the outcome builds systematically on individual sub-patterns defined by the starting condition . This linearity creates opportunities for simplifying complex dynamics into manageable predictive states, crucial for broader theoretical applications .