C/C++ Interactive Guide/c-cplusplus-interactive-guide.iso/c_ref/csource4/245_01/lca.doc

Text File | 1987-10-28 | 31.4 KB | 546 lines

[LCA.DOC]
[Harold V. McIntosh, 20 May 1987]

1. History.

Cellular Automata have been studied as a part of the abstract theory of
computation since the time that John von Neumann became interested in the
possibility of constructing self-reproducing automatic factories. Since
actual factories and physical machinery involve a myriad of practical but
non-essential details, he eventually followed a suggestion of Stanislaw Ulam
that an abstract mathematical model would be more amenable to a demonstration
of the possibilities of universal construction and self reproduction. He
worked out a scheme for such an automaton, in terms of a cellular space
occupying a two dimensional grid, in which each cell would be found in
one of twenty eight states.

The details of von Neumann's construction remained unpublished at the time
of his death, but were subsequently edited and published by A. W. Burks.
Ulam's work on functional iteration and his experiments on nonlinear mappings
was reported in conference proceedings, and cellular automata became a topic
in the theory of abstract machines, along with the work of Edward. F. Moore,
Claude Shannon, and others. Of course there were even earlier beginnings, in
the studies of Warren S. McCulloch and Walter Pitts in 1943 on neural nets,
followed in 1951 by a certain mathematical abstraction by S. C. Kleene, and
even in the general ideas on Cybernetics introduced by Norbert Wiener in his
famous book.

Public awareness of cellular automata can mostly be attributed to John Horton
Conway's interest in finding a simpler configuration than von Neumann's
and exploring its capabilities. Some of his results were presented in 1970 as
an ecological game called Life, at a time when such concerns were popular, in
Martin Gardner's monthly Mathematical Games column in Scientific American.
For a period of about three years Robert T. Wainwright maintained a quarterly
newsletter disseminating discoveries made by Martin Gardner's readers, some
of which were followed up in later columns in Scientific American. Many of the more
interesting results were obtained with the help of the graphics facilities
of a PDP-6 computer in MIT's Artificial Intelligence Laboratory.

When microcomputers began to attract popular attention, Conway's game of Life
became one of the early inspirations for an application; Cromemco's "Dazzler,"
a color video controller and one of the earliest peripherals, was frequently
used to display the evolution of Life configurations. An early issue of Byte
magazine summarized many results which had appeared in Wainwright's newsletter
a decade earlier, but had still not reached mass circulation. Some other
magazines, such as Omni, revived the topic, and in recent years Scientific
American has returned to the subject, most recently in A. K. Dewdney's
Computer Recreations, the current successor to Martin Gardner's column.

Professional scientific interest has received a considerable impetus from
the investigations of Stephen Wolfram, who undertook a computer based
search through the properties of one dimensional automata, guided by some
concepts from the realm of nonlinear dynamics and statistical mechanics.
In any event, the microcomputers, programming languages, and video displays
which are currently available are sufficient for many experimental studies
of cellular automata, many of whose results have considerable artistic merit.

A recent article exploring the aesthetic side of automata theory was one
entitled Abstract Mathematical Art, by Kenneth E. Perry, which appeared in
the December, 1986, issue of Byte. The article included a Basic program for
use on IBM/PC compatible computers, with indications that a Pascal version
was available from the magazine, and a statement that the author himself
had used machine language to quickly seek out the examples enumerated in his
article. Several of them were shown in striking color photographs.

The idea of a one dimensional cellular automaton is quite simple, an its
evolution in time is ideal for a two dimensional presentation, as on a video
screen. To start with, a cell is a region, even a point, with differing forms,
called states. For convenience, these states are usually numbered with small
integers beginning with zero, rather than described. For the purposes of
automata theory the nature of the states does not matter, only their relation
to one another, and the way they change with time according to their
envoironment. Since they are abstract, they can just as well be represented
by colored dots on a video screen, which is what leads to interpreting them
as part of an abstract artistic design.

To make a one dimensional automaton, a series of cells is strung out in a
line, the simplest assumption being that all the cells have the same number
of similar states, and that the rules of evolution will be the same for all
of them. The idea of forming the cells into a line implies a linear order,
but of course other arrangements are possible, both in terms of the dimension
and the connectivity of the cells. This is the second element of definition
for a cellular automaton - the relationship between the cells, or the kinds
of neighborhoods which they form. Again, the simplest neighborhood would
consist of a cell and its nearest two neighbors, and generally speaking we
would take a neighbborhood to consist of r neighbors on each side, giving
2r+1 for the total number of cells in a neighborhood.

There are some small quibbles to be made. If a chain is finite, it has ends,
which surely do not have the same neighborhoods as the interior cells. Either
they can be treated differently, or the chain can be imagined to close into
a ring, which would preserve the uniformity of all the neighborhoods. Also,
it is considered preferable to work with symmetric neighborhoods, each one
centered on its own cell, rather than worrying about irregular neighborhoods.
An exception occurs because there are times when only one neighbor would be
desired, always on the same side.

Thus there arises the notation (k,r) for a linear cellular automaton which
has k states within each cell, and such that it, together with r cells on
either side, is considered to form a neighborhood.

There is one final ingredient in the definition of a cellular automaton,
which is the rule of transition by which the cell changes state from one
generation to the next, conventionally assumed to be the same rule for each
neighborhood. It is the judicious selection of a rule as much as anything
that makes a particular automaton interesting or not.

Conway's game of Life was the result of a particular choice of rule for a
two dimensional binary automaton - two states per cell - whose neighborhoods
contained the cell in the center and the eight cells touching it, four of
them laterally and four of them diagonally. The announced critera by which
that particular rule was chosen were that a field of cells should neither
dwindle away to nothing - all zeroes - or eventually fill up completely -
all ones. Reportedly, he examined many different rules before choosing the
 particular one which gave us his famous game; even so, so much variety was
encountered with that one particular rule that years passed before many
others were studied.

Wolfram's recent work, mostly done at the Institute for Advanced Studies in
Princeton, systematically examined all the possible rules for one dimensional
automata. His recent book summarizes his and some other results in an extensive
appendix. In two dimensions there are far too many possibilities - more so
even than in one dimension - for there to be a chance to try everything, even
with a very fast computer. Notwithstanding, Dewdney's column in a recent issue
of Scientific American describes a three dimensional variant of Life examined
by Carter Bays. However, the one dimensional automata of type (2,1) represent
a reasonable starting point for systematic studies.

For such an automaton, a neighborhood contains three cells, while each can
have two states, so altogether there are eight possible neighborhoods. Since
there is nothing to require evolution of a given neighborhood to lead to one
value of the new cell or another, there are 256 possible ways that each of the
eight possible neighborhoods can evolve into the next generation, starting
with the possibility that everything evolves into zero and ending with the
possibility that everything evolves into ones. The easiest way to enumerate
the possibilities is to make up a binary number whose eight digits tell
how the neighborhoods 000, 001, 002, and so on evolve.

Unfortunately, the number of possibilities increase drastically if either
the number of states for a single cell increases, or the number of neighbors
increases. Thus a (3,1) automaton - three states with nearest neighbors -
has 3*3*3 or 27 neighborhoods, and the total number of possible rules would
be 3 to the power 27, somewhere on the order of 10 to the power 12, so they
are not soon going to be studied one by one. Alternatively, the combination
(2,2) would have 32 different neighborhoods, and thus 2 to the power 32
different rules, which is "only" in the range of 10 to the tenth power.

To obtain a reasonable sampling of even the smaller linear automata, Wolfram
used the idea which was already implicit in Conway's statement of his rule,
that the evolutionary criterion should depend on the number of cells in the
neighborhood, but not on their particular arrangement. Talking in such terms
reveals some hidden assumptions about our vocabulary. In Conway's binary
game, zero represented a dead cell, one a live cell, and his rules were
stated in terms of the number of live cells in the neighborhood. It is a
simple extension of this idea to assign numbers (weights, if you wish) to
the states, and make the transition depend only on their sum. A rule gotten
this way is called a totalistic rule; not all rules are totalistic, but they
lead to a more manageable sampling of all the possible rules.

2. The program collection.

This disk contains two kinds of programs. The first group consists of:

    LCA21.C - evolution of (2,1) automata
    LCA22.C - evolution of (2,2) automata
    LCA23.C - evolution of (2,3) automata
    LCA31.C - evolution of (3,1) automata
    LCA32.C - evolution of (3,2) automata
    LCA33.C - evolution of (3,3) automata
    LCA41.C - evolution of (4,1) automata
    LCA42.C - evolution of (4,2) automata
    LCA43.C - evolution of (4,3) automata

These nine programs are all quite similar, but since they each contain a
distinct selection of sample rules, and since there are slight differences
in indexing and ranges of indices, they are included as separate programs.

The second group of programs contains:

    ONE31.C   - cycles and gliders of period 1 for (3,1) automata
    ONE32.C   - cycles and gliders of period 1 for (3,2) automata
    ONE41.C   - cycles and gliders of period 1 for (4,1) automata
    ONE42.C   - cycles and gliders of period 1 for (4,2) automata
    TWO31.C   - cycles and gliders of period 2 for (3,1) automata
    TWO41.C   - cycles and gliders of period 2 for (4,1) automata
    THREE31.C - cycles and gliders of period 3 for (3,1) automata
    THREE41.C - cycles and gliders of period 3 for (4,1) automata
    FOUR31.C  - cycles and gliders of period 4 for (3,1) automata

which are likewise all fairly similar.

The cycle programs are based on the concept of a de Bruijn diagram, which is
much used in shift register theory. If a neighborhod is the string of cells
just sufficient to determine the evolution of its central cell, we can see
how neighborhoods might be strung together to determine the evolution of a
whole sequence of cells. Let us say that in succession we abandon the left
cell of a neighborhood and add new cell on the right. We are now ready to
calculate the evolution of the cell to the right of the original cell; by
repeating the process we can work out the evolution of a whole series of
cells.

In this process there is always an overlap of a fairly long string of cells;
however, just two for a (2,1) automaton. These cores can be laid out in a
diagram, a long string would be the easiest conceptually but it is more
practical to arrange them as nodes in a plane, labelling each with whatever
sequence of values the core cells might have.

Next, these nodes can be linked together according to the way they overlap
when used to form a longer chain. Thus there are two outgoing links for each
node, and two incoming links, for the (2,1) automaton: 01 could be followed
by either 10 or 11, and could be preceded by either 00 or 10. Generally, a
(k,r) diagram would have k to the power 2r nodes, each of them with k in links
and k out links; this full diagram is called a de Bruijn diagram for k symbols
and 2r stages.

The de Bruijn diagram lays out the possibilities; among its other uses it can
disclose how many distinct words of r letters can be made up within an alphabet
of k different letters. But we are interested in another application - finding
sequences which do not change as evolution goes on, for example. Since the
links in a de Bruijn diagram are just long enough to calculate one generation
of evolution for one cell, we can make comparisons with the original cell. If
the central cell evolves into itself, it qualifies for a still life. If it
evolves into its left neighbor, it qualifies for a right-shifting string. many
other variations are conceivable - for example a binary cell might evolve into
its complement.

Some of these properties - shifting, but not complementation, for example - are
consistent with the rule of evolution from generation to generation. That is,
shifting will not affect evolution because evolution has been assumed to
follow the same rule for every cell. But only in certain cases will we find
that complements have a complementary evolution. Going beyond binary automata
there are many more opportunities for the permutation of states, and there
will always be certain automata which incorporate this symmetry into their
rules of evolution.

Thus, to find all the sequences of states which do not change from one
generation to another, we only have to mark out the links in the de Bruijn
diagram for which the central cell does not change, and build up strings of
cells all sharing this same property. A similar construction applies for
shifting states.

Ultimately we are interested in cycles of the de Bruijn diagram, not the
transients leading into them, because these are the chains which can form
either rings of cells or chains infinite in both directions. The set of cycle
programs each works out these loops, and displays them on the console. The
process just outlined gives results valid for one generation of evolution,
but similar ideas apply to two, three, or more generations. The requirement
in each case is for a string long enough to produce the evolution desired;
the diagram then shows how to join these strings together into arbitrary
sequences.

Similar ideas can be used to find sequences which evolve into zeroes or
other constant values in so many generations. All calculations require
diagrams whose size grows exponentially with the radius of the neighborhood
or the number of generations of evolution involved. Thus, only the smallest
values of these parameters are feasible within the memory size available to
the programs, or the length of time needed to obtain the results.

A third group of programs is concerned with spatial periodicity rather than
temporal periodicity; in other words it is concerned with the possible
periods of cycles in a chain of length n. In contrast, the objective of
the second group of programs was to find the states of a given period, no
matter what the length of the ring. Now the length is fixed and we want to
know the possible periods.

The programs are:

    CYCLE21.C - periods of (2,1) rings
    CYCLE22.C - periods of (2,2) rings
    CYCLE23.C - periods of (2,3) rings
    CYCLE31.C - periods of (3,1) rings
    CYCLE32.C - periods of (3,2) rings
    CYCLE41.C - periods of (4,1) rings
    CYCLE42.C - periods of (4,2) rings

The computation is similar to the one carried out for the de Bruijn diagram,
but the basic element is one of the k to the nth possible strings of cells.
The evolution of each one of them is computed and stored in an array. There
can be but one second generation successor to each first generation string,
not the k to be found in the de Bruijn diagram; otherwise the analysis is the
same. The results are the periodic cycles, reported as a series of pairs of
strings and evolutes.

Programs from all three groups will prompt for the information they need. For
a cycle analysis, the first requirement is the rule number. For a totalistic
automaton, it would consist of the string of values to be assigned to the
respective sums 0, 1, 2, and so on. Only for the program LCA31 is storage
space sufficient to work with the 27 values which can be assigned all the
distinct values of three states; a totalistic rule number can be given, as
well as a full specification.

The evolutionary programs contain a selection of stored rules, selected from
many random choices to illustrate some particular points of evolution, or just
because they looked nice. One of these is selected, somewhat at random, along
with a random initial line, all ready to run, when the program is started. If
the initial choice is not wanted, or after the first run has completed, any of
the data can be edited in preparation for the next run.

If the display turns out to be uninteresting, or there is no desire to wait
out the full 45 seconds which it requires, striking any key will stop it.

3. What to look for.

To watch the evolution of an arbitrary linear automaton from a random initial
configuration is to see a great deal of confusion. Gradually - in some cases
quite quickly - it becomes apparent that each rule of evolution has its own
personality, and that as rules and types of automata are varied, similarities
are as apparent as differences. This is presumably what lead Conway to seek
out rules for which configurations eventually settled down to simple activity
rather than disappearing entirely, remaining motionless, or filling up the
entire space.

Wolfram laid down a serviceable classification into four categories

    class i - evolution to a uniform state
    class ii - evolution to isolated cyclic states
    class iii - evolution to comprehensive cyclic states
    class iv - evolution to complex isolated states

which were derived from some classifications in nonlinear mechanics. His
attention was particularly attracted to the class iv states. It seems that
these are to be found for rules whose de Bruijn diagrams contain certain
loops. These can be readily detected for short periods at least.

A good starting point, having selected a specific rule, is to work out a
table of periods (time repetition) and cycles (space repetition) in which a
given row shows the number of cycles of given period in rings of length given
by the columns. Entries for an entire row can be deduced successively from the
programs ONEIJ, TWOIJ, THREEIJ, and so on. It may be a bit disappointing that
so few rows can be obtained within the limits of computer memory and running
time that presently exist. Nevertheless, the exponential growth of resources
required ensures that rows or columns will only be added one at a time, and
gradually at that. Still, a few rows can actually be done, and the information
obtained can be quite informative.

The columns of this table can be found from the CYCLEIJ series of programs;
again practical considerations limit the lengths of the rings studied to the
order of ten; more for binary automata and less for those with more states.

Certain theoretical conclusions do not depend on practical limitations. For
example, a there are at most k to the power n rings of n cells in a (k,r)
automaton, and evolution is uniquely defined. Some ring must repeat itself,
no matter what the starting ring, after k to the power n generations; more
than that can't all be different. In practice, the number of generations
elapsing before repetition is a very small compared to the absolute maximum.
In any event, there is an exponential (but finite) limit to the periods shown
in the period-cycle table.

Statistics of interest concerning the cycles include: the number of cycles and
their lengths, the height of the transient trees leading into the cycles, and
the convergence factor at each node of these trees.

The rows of the table can be found from the de Bruijn programs; since 2r+1
cells are needed to ascertain a generation of evolution, only about half as
periods as cycles can be worked out for a given quota of computer resources.
Similar theoretical conclusions are possible, since the periods are gotten
from a subset of the de Bruijn diagram. A 2r-stage de Bruijn diagram for k
symbols has k to the power 2r nodes; k times as many links. Once this number
of links has been used up in constructing a path through the diagram, one of
them would have to be repeated. Thus there is also an exponential upper bound
in the rows of the period-cycle table. For example, if an automaton has a
cycle of period 2, it must already show up in some short ring; if it has not
appeared in rings below a certain limit, it will never appear in longer rings.

Similar statistics can be compiled for the de Bruijn diagrams: the number of
periods and their lengths, the number of transients leading into loops, and
the corresponding convergence and divergence factors. Failed loops are still
interesting, they correspond to strings which are periodic, but which dwindle
away with each generation.

Both the cycle diagrams and the period diagrams may have intersecting loops;
this simply means that choices are present at certain junctures in working up
a chain of cells with a certain property, leading to a greater variety of
sequences than would oherwise occur. This choice is particularly vivid in the
de Bruijn diagram when one of the loops consists of a single node of identical
cells embedded in another loop, since these can be strings of Wolfram's class
iv.

Although the de Bruijn diagram can be used to reveal the periodicities of a
given cellular automaton, it can also be used in automaton synthesis. That
is, desired loops can be marked out first in the diagram, and then a rule
chosen which respects the links. For period 1 properties the mapping has to
be direct, since each link in the de Bruijn diagram corresponds to a distinct
neighborhood in the automaton. Including or excluding it from the period
diagram either determines or limits the value of the transition for that
neighborhood. For longer periods the evolution corresponds to a composite
rule, which may or may not be factorizable in the requird manner.

Another use of the period diagram is to obtain ancestors of a given chain.
The simplest application is to find the ancestors of constant chains, which
follows readily from the fact that each link represents the evolution of the
central cell in one neighborhood. All the links evolving into zero determine
the chains which must evolve into zero; conversely demanding that given loops
evolve into zero determines the rules for which such an evolution is possible.
For a binary automaton, it would determine the rule uniquely. An interesting
exercise is to show that for totalistic automata, the ancestor diagram for
constant chains consists of pure loops, without any transients at all.

More subtle than Wolfram's class iv automata is the fact that some automata
seem to exhibit natural barriers. For some rules it is observed that there
are areas of independent evolution, which seem to go about their business
independently of what is happening in other regions. Consulting the de Bruijn
diagram, it is found that there are certain nodes, for which all incoming or
outgoing links survive in the period diagram, even if they do not continue
on to form closed loops. It is only necessary that there is an unbroken chain
from a node with complete incoming links to another (possibly the same) with
complete outgoing links. Clearly, certain partial variants on this theme are
also possible.

Historically, de Bruijn diagrams were created in order to solve the problem
of finding all the distinct sequences of certain symbols. This idea can be
applied to a period diagram, by asking whether all possible sequences of cells
can appear as possible evolutions. Since the period diagram is a restriction
of the de Bruijn diagram, it may be suspected that they may not; this confirms
the existence of "Garden of Eden" states for cellular automata. These are
chains of cells which can only be seen as intital states for an automaton,
because they have no ancestors and cannot arise during the course of evolution
from any other states.

The programs in the present collection do not detect Garden of Eden states,
but they can be found by using state sequencing techniques from the theory
of automata, or from a detailed examination of the chains produced by the
cycle programs, which are not presently included in the display produced by
these programs.

Binary automata may be judged to be less interesting because they "don't do
anything" or fall into Wolfram's classes i and ii; but there are other ways
in which automata with larger numbers of internal states can fall into a
pattern of restrictive behaviour. For many rules, watching the screen display
for a while will reveal that one of the colors has disappeared. This would be
especially noticaeable for a rule in which one value never appeared in the
rule, because it would have to be be absent in all lines after the first.

Generally speaking, we would be dealing with a subautomaton - one for which a
subset of states could be found which was closed under evolution. That is,
states in that subset would evolve only into each other and into no others.
Many automata show extreme examples of this behaviour - dead states evolve
only into dead states, using Conway's metaphor. Thus a whole class of automata
comprised of those with a quiescent state, could be characterized by saying
that the quiescent state belonged to a subautomaton.

There is another mathematioal concept related to subsets, which is the idea
of equivalence relations. According to this concept, two or more states of
the automaton might be regarded as being interchangeable. If not actually
identical, there is no essential difference between them. Watching the
evolution of certain automata on the screen, there sometimes seems to be
a wash of color laid over an underlying pattern. The pattern seems to evolve,
while the color overlay has a life of its own. This is an example of a factor
automaton, in which the overlaid color is equivalent to black, the general
background in this series of programs.

Finally, there are mappings from one automaton to another. One of the simplest
examples would be complementing all the cells of a binary automaton. The
complemented automaton would probably not evolve according to the same rules,
but it might. For automata whose states are represented by television colors,
interchanging the colors would be such a mapping. Aesthetically the difference
is striking, but mathematically it is the same automaton.

It is instructive to tinker with both the initial array and with the rule of
evolution of an automaton. The LCAIJ programs include a generator of random
numbers which can be used to either set up a rule or the initial array. The
numbers generated do not often have long runs, but an interesting aspect of
most automata is to see how they evolve when the initial state contains some
long runs, particularly of a quiescent state. An option allows generating
such a state; an editing option allows a complete revision of the initial
state. Some programs have an undocumented feature which allows copying the
initial eighth of the pattern, which has the practical consequence of forcing
the arrival at the final cycle more rapidly. The typical lengths of transients
increases with ring length, and lies in the hundreds or thousands for rings of
length around 20. Thus, the transient time would be extremely long for the
video line used by these programs.

For some rules patience is required to obtain an initial state which shows
some of the more delicate class iv objects, and recourse to the de Bruijn or
cycle programs may be necessary to see what the interesting structures are.

Knowing how barriers, cycles, and class iv separating intervals are related
to the de Bruijn diagram, the evolutionary rule may often be adjusted to make
a promising rule show cleaner or more desirable behaviour. This adjustment
is necessarily indirect for those programs which only use totalistic rule
specifications, but for those programs in which the direct parameters are
sufficiently few, the rule can be tailored exactly.

If the totalistic rules do not allow such fine adjustment, they do have a
statistical property which is useful. There are more ways to form sums in
the middle range than for the extremes; one might think in terms of the
binomial distribution. Thus the values assigned the middle range will be
relatively influential in determining the overall behaviour of the automaton,
while the extremes can be used for fine adjustments. One extreme determines
what happens to long sequences of zeroes, the other to long sequences of
k-1's, and in both cases to sequences in which these extremes dominate. This
also means that the near extremes determine what happens to the fringes of
regions dominated by the middle values.

Of course, there ia a whole art to trying to read out general features of
the automaton directly from its rule specification.

4. References.

Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning ways for
your mathematical plays, Academic Press, 1982  (ISBN 0-12-091152-3) vol. 2,
chapter 25

D. Buckingham, Some facts of life, Byte 3 (1978) p. 54

A. K. Dewdney, Computer Recreations - Building computers in one dimension
sheds light on irreducibly complicated phenomena, Scientific American, May
1985, pp. 10-16.

Martin Gardner, Mathematical Games, Scientific American, October 1970

Fred Hapgood, Let there be Life, Omni, v. 9, #7 (April 1987) pp40-46, 116-117.

Brian Hayes, Computer Recreations - The cellular automaton offers a model
of the world and a world unto itself, Scientific American, March 1984,
pp 10-16.

Stephen Levy, Hackers: Heroes of the computer revolution, Anchor Press/
Doubleday, Garden City, New York, 1984 (ISBN 0-385-19195-2), chapter 7.

O. Martin, A. Odlyzko, and S. Wolfram, Algebraic aspects of cellular automata,
Communications in Mathematics and Physics 93 (1984) p.219

John von Neumann, Theory of self-reproducing automata (edited and completed by
A. W. Burks), University of Illinois Press, 1966.

Kenneth E. Perry, Abstract mathematical art, Byte, December 1986, p. 181.

William Poundstone, The recursive universe, William Morrow and Company, New
York, 1985 (ISBN 0-688-03975-8).

Kendall Preston, Jr., and Michael J. B. Duff, Modern cellular automata, Plenum
Press, New York, 1984 (ISBN 0-306-41737-5).

S. Ulam, On some mathematical problems connected with patterns of growth
of figures, in A. Burks (ed.) Essays on cellular automata, University of
Illinois Press, 1970.

Stephen Wolfram, Statistical mechanics of cellular automata, Reviews of Modern
Physics 55 (1986) pp. 601-644.

Stephen Wolfram, Theory and applications of cellular automata, World Scientific,
1986 (ISBN 9971-50-124-4 pbk)

[end]