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

Text File | 1980-01-01 | 14.4 KB | 283 lines

LCAU.DOC

This disk is a supplement to the disk "LCA.C" which was released in
Summer, 1987. The original disk contained 9 programs written in "C" to
calculate and display the evolution of linear cellular automata.
Although the programs represented a point in the evolution of the
course Fortran III offered during the past several semesters, and were
promoted at the XVI Feria de Puebla, they also had a strong
inspiration in an article in the December, 1986, issue of Byte magazine
which explained how cellular automata could lead to interesting
abstract mathematical art.

    Kenneth E. Perry, Abstract mathematical art, Byte,
    December 1986, pages 181-192.

The 9 programs in the LCAkr.C set ran through the range of 2, 3, and 4
states per cell, as well as interactions between first, second, or
third neighbors. The combinations (4,1) and (4,2) are probably the most
colorful, but the binary first neighbor version (2,1) is more amenable
to an exhaustive analysis.

Programs in the new series are named LCAU to distinguish them from
members of the old series.

In the old series, In all cases except for (2,1), only totalistic rules
were considered. Totalistic rules are those for which the transition
depends only on the number of cells of different kinds in each
neighborhood, but not on their precise arrangement. More exactly, each
state gets assigned an integer in the range 0 to k-1 as a weight, the
actual transition being a function of the weighted sum of all the
neighbors (including the evolving cell). The artistic effects arise
from assigning colors to each of cell values.

Although the use of totalistic rules serves to reduce the enormous
number of possible automata greatly, it excludes many interesting
possiblilities arising from a more detailed specification of the
evolutionary rules. When k, the number of states per cell is small,
there is not too much which is possible in the way of design, but once
it reaches 4 or beyond some interesting constructions become possible.
LCA41.C in particular, contains enhanced rule and line editing menus
which allow experimentation with the design of rules.

Certain of the demonstrations in LCAU41.C show how the design process
can be used. There is an example of a "binary counter'" which consists
of a glider gun together with bistable targets. In one state the target
absorbs the glider and changes to the other state. In the second state
the target passes the glider, reverting to the first state. Thus half
the gliders are lost to each target, whose state forms a binary counter
whose carry is represented by the gliders which are allowed to pass.

Another demonstration shows how a bouncing glider may shuttle between
two obstacles - still lifes - drawing them ever closer together. Just
as the glider is about to be crushed, the walls coalesce but the glider
escapes to one side, seeking new walls to conquer. Multiple gliders may
go about their business, competing for the wall if they lie on opposite
sides or hastening the squeeze if they lie on the same side.

A third demonstration shows a slow glider propelled by an intrenal
glider or gliders bouncing back and forth - a sort of Mexican jumping
bean. When a fast glider overtakes a slower glider, they coalesce,
producing an even slower glider.

A fourth demonstration shows gliders of two different velocities, which
can be used to set up a remote still life whose reaction to further
gliders gives it a life of its own.

Such constructions can be used to generate interesting patterns, but
they also serve theoretical ends as well. For example, the binary
counters establish the existence of structures with both exponentially
long transients and exponentially long cycles. Since they still use
several cells to establish the basic components and their spacings,
they still do not reach theoretical maxima; but they do lie within
certain factors of such maxima.

When k becomes larger still, universal Turing machines can be
programmed, but this probably requires a k of at least 6 or 8.

Another extensive addition which has been made to the programs is to be
found in the series PROB.C, which can be invoked by typing "t" in the
main menu (the old totalistic rule number can still be utilized by
typing "T"); in fact their inclusion more than doubles the size of the
programs. These new programs permit a statistical survey of the
properties of the automaton. Originally they calculated simple
probabilities on the basis of ideas which go by the name of "mean field
theory," whose results were plausible but not entirely convincing.

Since then two interesting articles have appeared [the second as a
preprint]:

    W. John Wilbur, David J. Lipman and Shihab A. Shamma, On the
    prediction of local patterns in cellular automata, Physica
    19D 397-410 (1986).

    Howard A. Gutowitz, Jonathan D. Victor and Bruce W. Knight,
    Local structure theory for cellular automata, Physica 28D
    18-48 (1987).

These articles, from differing points of view, show how to take
correlations between cells into account by calculating the
probabilities of strings of cells. Rather than taking individual
probabilties as fundamental and deducing the probabilities of
combinations, the process is inverted; self consistent probabilities
for strings (or blocks) of a certain length are found from which the
probabilities of individual cells are obtained by averaging.

The calculations of these articles have been included among the options
of the "t" submenu, so that probabilities derived from blocks of length
up to 6 can be compared with simpler estimates and with the actual
performance of the automaton.

A third feature of the new series is the incorporation of the de Bruijn
diagrams within the main program, together with a visual representation
in terms of chords of a circle. It is still not possible to transfer
the cycles obtained back to the main program without copying them on
paper and editing the initial line with the option "l". Limitations of
space and time severely restrict the lengths of periods which can be
analyzed. Although interesting gliders and cycles are found within the
accessible range of the program, there are many others of longer
periods which manifest themselves experimentally when the evolutions
are run. It would be nice if the exhaustive analysis afforded by the
de Bruijn diagrams were feasible for the longer periods that show up on
the screen, but they would really require a faster computer, more
memory, and probably programs incorporating finer details of the
algorithms used.

The programs contain a bare minimum of help facilities, in the sense
that menus of one type or another are presented at various stages in
the evolution of the programs, and others are sometimes available by
typing a question mark, just as a slash will often clear portions of
the screen.

A manual consisting of the lecture notes for Fortran III is in
preparation, for which chapters are planned describing the accompanying
programs. As is well known, the preparation of manuals always lags the
evolution of the programs which they are supposed to describe.

There are still some interesting problems of presentation - recall that
Fortran III is supposed to be dedicated to graphical techniques!
Presentation of simple evolution is easily solved, since the resolution
and velocity of the graphics controllers included as standard equimpent
in IBM PC's and clones is adequate. Unfortunately color monitors and
their controllers are sometimes seen as premium equipment which was not
included in a given installation, so that a monochromatic rendering of
the color displays must be endured.

Even so, the speed and screen resolution which is available in the
present generation of equipment is only marginally satisfactory, having
only a fraction of the resolution of pen and ink plotters which have
been commonly available. Once statistics pertaining to the evolution of
automata are to be presented, it is found that there are many more
parameters than are comfortable, which leads to the use of shading,
complex surface representations, even stereographic views. It is in
this area that some interesting results can be obtained, but mostly
ones which whet one's appetite for the next generation of equipment.

Likewise the use of the de Bruijn diagram and the reduced evolution
diagram, even without their probabilistic versions, requires line
drawings of a complexity which quickly surpasses the capability of the
present generation of graphical displays. Although the complexity of
these diagrams increases exponentially - making even modest values of
parameters permanently inaccessible; still, even moderately better
graphics equipment will permit an instructive display of the simplest
cases.

Although the menus vary slightly from program to program, they
generally conform to the following pattern:

The Copyright Notice - The initial screen in all programs bears a
copyright notice and a very short description of the program. While the
inexperienced user is reading the screen, a random number generator is
wasting time, so that there will usually be a different display every
time the program is run, likewise a different sequence of random rules
and initial lines. No effort has been made to see how much this initial
idling degenerates the performance of the random number generator.

The Main Menu - The main menu generally offers the following selection:

    r - edit the rule
    l - edit the line
    q - quit
    g - graph the evolution
    x - generate a random rule
    y - generate a random line
    u - generate a sparse line
    T - edit a totalistic rule number
    D - display all stored rules in sequence

    #nn - execute stored rule number nn
    @nn - execute totalistic rule number nn
    $nn - execute 12 totalistic rules starting with number nn
    wnn - execute Wolfram rule number nn (LCAU21 only)

    t - enter probabilistic submenu
    d - enter de Bruijn submenu

Additional commands are present in different programs, but they are not
publicized because they are generally experimental. In future versions
of the programs they may be officially documented. Anyone persisting in
a desire to use them at their own risk may discover them by studying
the source code. For example, a Z will sometimes clear the line of
cells, a dot will often execute a single generation of evolution but
still within the main menu.

The Rule Editing Menu - To edit a rule, either general or totalistic,
one may move the cursor and insert values for the cell above the
cursor. Some programs have a more elaborate cursor, with tabs,
wraparound, and the possibility of flagging values which will not be
altered by using the random rule generator x (X overrides the flags).
Again these features are experimental, and may possibly be confirmed in
future versions of the programs.

The Line Editing Menu - Lines are edited by essentially the same
procedures that the rules are, but the long line of 320 cells is broken
down into 8 lines 40 cells, to make movement across the line using the
up and down arrows more rapid. LCAU41, which corresponds to one of the
simplest automata for which rules may be designed to order, has many
additional line editing options, all experimental, which can be used to
facilitate the design. No doubt more will be added before the existence
of all of them is officially announced.

The Probabilistic submenu - By typing t one arrives at a separate
display, implemented in the programs PROB.C, which will perform several
statistical analyses of their automata. The programs vary considerably
with the number of states, since they attempt to represent the relative
probabilities as points within a simplex. For two states, the results
are trivial, for three states the diagrams are planar and interesting,
for four states the graphical capabilities of the screen are strained;
for five and beyond some other representation would be requiered.

The generic options are:

    a - a priori estimates
    m - evolution of cells and pairs
    M - 50 generation evolution of cells and pairs
    g - 50 feneration evolution of single cells
    G - 200 generation evolution of single cells
    s - graph probabilities in stereo
    t - graph probabilities, show contours in simplex
    1 - 1-block local structure theory iterations
    2 - 2-block local structure theory iterations
    3 - 3-block local structure theory iterations
    4 - 4-block local structure theory iterations
    5 - 5-block local structure theory iterations
    6 - 6-block local structure theory iterations
    + - select red-green-yellow
    - - select blue-cyan-white
    e - show 16 lines of evolution
    / - clear screen
    ? - show menu
    carriage return - exit

Options 5 or 6 may not be available if they require too much time or
space, t shows two-block probabilities for k=2 automata, and there may
be variants on s. For k=2, the commands x, y, z, w, v, i, and j produce
graphs for self-consistent 1-block probabilities for varying numbers of
generations and numbers of iterations.

The de Bruijn submenu - There are two kinds of de Bruijn diagrams that
can be computed - those showing the counterimages of a uniform string,
and those which isolate strings satisfying a certain combination of
shifting and periodicity. Letters are assigned to them consecutively,
but the combination of period and displacement varies widely because of
the differing number of combinations possible. Generally

    1,2,...        generates a de Bruijn diagram of n stages
    a,b,c,...    shows cyclic counterimages
    A,B,C,...    shows all counterimages
    other letters    show (p,d) cycles
    +,1        selects the color palette
    ?,/        clears screen, shows menu
    carriage return exits

To obtain information from the de Bruijn submenu will probably require
the use of pencil and paper, or the use of the screen dump program.
Although the program lists all the links in the de Bruijn diagram, the
ring diagram is generally too cluttered to use directly from the screen
and should be redrawn. Usually the resulting diagram can be further
simplified, often it contains many redundant loops. Used casually, it
still shows whether there will be many or few periods of a given type.

Harold V. McIntosh
April 15, 1988