LCAU.DOC

Harold V. McIntosh
Departamento de Aplicación de Microcomputadoras,
Instituto de Ciencias, Universidad Autónoma de Puebla,
Apartado postal 461, 72000 Puebla, Puebla, México.

January 11, 2025

Abstract:

A previous collection of celular automata programs has been extended in three directions; also certain minor errors have been corrected.

General rules, not just totalistic rules, may be analyzed.
Cell densities and block probabilities may be calculated according to mean field theory and local structure theory using options in a new submenu.
An option to produce de Bruijn diagrams is incorporated in another new submenu.

Consequently a more detailed and convenient analysis of (k, 1), k = 2, 3, 4 and (2, 2) automata may be made than previously.

The disk LCAU.C supplements the disk LCA.C which was released in the summer of 1987. Both source code and a separate disk of .EXE files are provided. 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, at the Universidad Autónoma de Puebla, and were promoted at the XVI Feria de Puebla, they had their principal inspiration in an article in the December, 1986, issue of Byte magazine which explained how cellular automata could lead to intricate and complicated designs, with a certain aesthetic appeal.

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

The 9 programs in the LCAkr.C set ran through the k-range of 2, 3, and 4 states per cell, as well as interactions between first, second, or third neighbors (the r-range). The combinations (4,1) and (4,2) are surely 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 internal 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

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 a uniform pattern, whose constituents are described below.

**Figure:** copyright notice
$\begin{figure} \centering \fbox{\rule{0mm}{60mm}\rule{100mm}{0mm}} \end{figure}$

The Copyright Notice (Figure 1)

- 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.

**Figure:** the main menu, showing rule and line
$\begin{figure} \centering \fbox{\rule{0mm}{45mm}\rule{110mm}{0mm}} \end{figure}$

The Main Menu (Figure 2)

- The main menu generally offers the following selection, whose details vary slightly from one automaton to another:

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
#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.

The following list is fairly reliable, although the options do not appear on any of the screens presented to the user:

.: - the line evolves for one generation
=: - repeat the first 40 cells 8 times
: - repeat the first 20 cells 16 times
D: - display all stored rules in sequence
Y: - symmetrize the rule
Z: - (sometimes z) clear the line

The . instruction is particularly useful when an interesting structure has been found on the general screen, but it is evolving too fast or it is hard to pick out fine details clearly at the resolution of the screen. By returning to the main menu (using any keystroke followed by y) the evolution can be followed one generation at a time, and either recorded by a screen dump or noted by hand on a scrap of paper.

Similarly it is possible to transfer the results of the de Bruijn diagram or any other interesting string to the line menu, then return to the main menu to follow their evolution closely with the dot command.

The instructions which repeat the initial segment of the line can be used to increase the variance in some of the probabilistic studies, and to force the automaton to enter a cycle sooner than otherwise. Nevertheless, for most rules a ring of 20 cells is still much too long to reach a cycle within a thousand generations.

In contrast to the old programs, the new programs contain very few sample rules. By recompiling, one could add further examples that seemed worth preserving; in any event the command D allows the samples to be reviewed and thus is useful for presenting demonstrations. No doubt some future edition of these programs will allow rule files to be read from disk, as well as allowing the storage of interesting rules which have been found during the course of execution of a program.

**Figure:** the rule editor works on the bottom line of the array relating neighborhoods (top lines) to their image (last line).
$\begin{figure} \centering \fbox{\rule{0mm}{20mm}\rule{120mm}{0mm}} \end{figure}$

The Rule Editing Menu (Figure 3)

- 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. Later on the special commands which apply to LCAU41 are shown.

**Figure:** the line editor works on the line of cells, which is divided into 8 lines of 40 cells.
$\begin{figure} \centering \fbox{\rule{0mm}{35mm}\rule{120mm}{0mm}} \end{figure}$

The Line Editing Menu (Figure 4)

- 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.

**Figure:** a typical screen within the probabalistic submenu, showing the placement of the different options. Typing ? will summon the menu.
$\begin{figure} \centering \fbox{\rule{0mm}{85mm}\rule{124mm}{0mm}} \end{figure}$

The Probabilistic Submenu (Figure 5)

- 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 required.

The generic options are:

a: - a priori estimates
m: - evolution of cells and pairs
M: - 50 generation evolution of cells and pairs
g: - 50 generation 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 blue-cyan-white
-: - select red-green-yellow
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.

**Figure:** a typical screen within the de Bruijn submenu, showing the placement of the different options. Typing ? will cause the menu to appear.
$\begin{figure} \centering \fbox{\rule{0mm}{85mm}\rule{124mm}{0mm}} \end{figure}$

The de Bruijn Submenu(Figure 6)

- 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.

The de Bruijn submenu is entered by typing d in the main menu, to execute a program RIJN.C which is nearly self-contained. In general terms, the commands of the submenu are

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
+,-: - 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.

**Figure:** a typical screen showing the rule number and 192 lines of evolution
$\begin{figure} \centering \fbox{\rule{0mm}{110mm}\rule{124mm}{0mm}} \end{figure}$

Figure 7 shows a typical screen of evolution. Evolutionary screens may be interrupted at any line by pressing any key; alternatives will then be offered to continue the display (carriage return), exit the program (n), or return to the main menu (nominally y, but it is the default). It is a general principle in all parts of the program, that the keystroke which interrupts any activity is discarded. Therefore a new activity cannot be initiated by simply typing its letter, although typing it twice in succession will usually work.

Designing rules to order, which first becomes interesting for (4,1) automata, is a sufficiently interesting activity that it is worth documenting some of the otherwise hidden options in the main menu, rule editor, and line editor of LCAU41.C; nevertheless they are strictly experimental and may well be changed as experience in their use grows. In any event they require considerable skill.

main menu

- special commands for rule design

U: - push rule and flags
V: - pop rule and flags
G: - fetch rule and flags without popping
x: - random values for unflagged transitions
X: - random values for all transitions
1: - some particular transitions
2: - other particular transitions

rule editor

- special commands for rule design

0,1,2,3: - define transition
tab: - next quad = cursor fast advance
space: - advance cursor
back: - return cursor
up: - set flag
down: - remove flag

line editor

- special commands for rule design

0,1,2,3: - define cell
arrows: - move about cell array
< , >: - move to margin
z: - clear one row
Z: - clear entire line
x: - clear flags
q: - uniform color
=: - adapt rule to transition at cursor
*: - adapt rules to all transitions in one segment
.: - evolve cell under cursor
?: - evolve entire segment from the one above
/: - conditional evolution of segment (mark unflagged transitions)
c: - test consistency of one cell - inconsistent cell marked red
c: - test consistency of all cells - inconsistent cells marked red

**Figure:** evolution of a (4,1) rule whose behaviour is that of a binary counter
$\begin{figure} \centering \fbox{\rule{0mm}{85mm}\rule{124mm}{0mm}} \end{figure}$

Figure 8, on the next page, shows the evolution of a (4,1) binary counter. Many rules can be found in which gliders, still lifes, and oscillators go about various simple activities; it is only necessary to do a certain amount of experimentation. It is an open question as to what the minimum combination of states and neighborhood is needed to obtain the behaviour of a Turing machine, but some examples are known of one sided automata interacting with a single neighbor which suffice. Nevertheless there are many interesting combinations which are still less complicated than a universal Turing machine, some of which just might be universal in their own way.

end