about xlcau21 (22)

[McIntosh Harold V.-UAP]

Along with the role of Universal Algebra in the theory of cellular automata,
there is also the question of symmetry. For binary automata, there is not
much to be said since the only possibility is complementation. Given k states,
there are k! permutations of the state set, all of which qualify as congugates
or complements of a sort.

Reduction according to symmetry will always reduce the number of cases to be
considered, but given the even more rapid growth in the total number of rules
as k increases, the overall effect is nowhere as favorable as it is for binary
automata. In compensation, there are more symmetry classes of automata, and
more ways for automata to be highly symmetric.

The LCAU programs scan their rules looking for details such as symmetry,
totalism, and degeneration. The actual survey made has varied somewhat from
year to year, according to the way that interest in the results has changed.
The search for totalistic and semitotalistic automata is always useful, just
because of the reduction in parameters necessary to specify the automaton.
Moreover, those two categories are especially rich in Class IV automata,
whereas it is really difficult to find one haphazardly among general rules.

Of course, the symmetry of a state set always has to be extended according
to the symmetry of its neighborhood. For one-dimensional automata, the only
possibility is reflection, but as the dimension increases the symmetry can
grow accordingly. Since they are so restricted, consider the elementary (i.e.
(2,1) rules) automata: for complementation classes we have

000 001 010 011 100 101 110 111
--- --- --- --- --- --- --- ---
a b c d e f g h

with the requirements (* = complement) h=a*, g=b*, f=c*, e=d*. What is left
over gives 16 possibilities, but with spatial symmetry there is additionally
b=e and d=g, but these are redundant, leading to 8 choices. They give Rules
232, 204, 178, 150, 105, 77, 51, 23, of which only Rules 105 and 150 are at
all interesting (i.e., Class III). All of this information can be gleaned
from Wolfram's appendices.

Going on to three states, there are two kinds of permutations (besides the
identity). The two three-cycles are one, the three transpositions another.
Respect to the cycle (123), the neighborhoods group into the following orbits:

000 111 222

001 112 220 010 121 202 100 211 022
002 110 221 020 101 212 200 011 122

012 120 201
021 102 210

In the absence of reflective symmetry, the first member of every one of
these triads can be assigned an arbitrary image, leaving 3^9 possibilities.
With symmetry, some orbits coalesce, for a total of 3^6, still a pretty
large number. Another way to coalesce orbits would be to introduce the
transpositions, and if all of this were done, there would be four orbits.
But care is needed to ensure compatibility between the different orbit
decompositions; if they do not commute as equivalence relations, choices
may be further restricted.

When there are four states to consider, there are more possibilities. There
are 24 permutations of the state set, rather than simple complementation or
its absence, to consider. With nearest neighbor interactions, there are the
following subsets to consider, arranged according to whether they contain
one, two, or three distinct states. If there is reflective symmetry the first
and last of the 12-element lines should be joined; in any event, all of the
four 6-element lines go together.

000 111 222 333 4

001 002 003 110 112 113 220 221 223 330 331 332 12
010 020 030 101 121 131 202 212 232 303 313 323 12
100 200 300 011 211 311 022 122 322 033 133 233 12

012 013 023 021 031 032 6
102 103 120 123 130 133 6
201 203 210 213 230 231 6
301 302 310 312 320 321 6

Do we really need to permute the states to get a symmetric Rule? Above,
a permutation is required for the first line. Otherwise, suppose that
f(aaa)=f(bbb)=c. Then there is a permutation p which exchanges a and b but
additionally changes c. Then from
f(p(a),p(a),p(a)) = p(c)
follows
f(b,b,b) != c,
which is a contradiction. Since the states all require distinct images, f is
itself a permutation when applied to uniform neighborhoods.

But, given a three-state automaton, we could not both exchange a with b and
alter c, so that particular argument would fail.

It is not clear whether there have been any efforts to classify self-conjugate
automata beyond the (2,1) examples to be found in Wolfram's book and elsewhere.
The above remarks are hardly exhaustive, serving mostly to point out some
interesting experiments which could be performed, in search of this class of
automata.

They should also serve to explain the subject matter of the accompanying
illustration, "scnj.ps.gz.uu," showing a contour map in the three dimensional
space of the probability tetrahedron for a rule contrived to have high
permutational symmetry. Think of a tetrahedron seen in edge view.

This is a diagram which was not feasible in the MS/DOS version of LCAU due
to limitations of screen resolution in the CGA graphics. It is a complement
to the stereopair displaying contours of probability difference with colored
dots. Recall that the probabilities of the four states of a (4,1) automaton
are considered to be components of a vector to which mean field theory has
been applied; interest centers on the fixed points, which are surrounded by
contours of very small probability difference.

The slider at the bottom of the window adjusts the contour level. The box
marked "Levels" allows showing up to three contours, in different colors,
simultaneously, at values of c, 2c, and 3c. The illustration does not include
this to keep the size of the posting within bounds. There is also a selection
of mean field curves for one, two, or three generations of evolution.

There is still a problem of getting a three dimensional "feel" for these
contours. The "View" option selects front, side, or plan views so the object
can be glimpsed from three different directions. The presentation is more
effective if at least two of these views can be shown on the same screen
side by side. There is also no reason for not displaying the contours in a
stereopair, but both alternatives require a bit more than twice the width of
screen space that the single image requires.

The feel could also be improved by treating the contours as solid objects
and suppressing hidden lines. The contour scheme is to decompose every little
cube in a 25x25x25 array into six tetrahedra (defined by ordering the three
coordinates) and tracing the lines of intersection of all the faces with a
linearized approximation to the differences in the return map. Under favorable
conditions they appear to define little triangles, but then there is a whole
body of knowledge dedicated to graphical presentation and illusion. In fact,
the whole lore of image rendition is available to anyone who wants to take
advantage of it, the price being to make the whole program collection that
much bigger.

Harold V. McIntosh |Depto. de Aplicacion de Microcomputadoras
mcin...@redvax1.dgsca.unam.mx |Instituto de Ciencias/UAP
(+52+22)43-6330 |Apdo. Postal 461
(+52+22)43-6057 |72000 Puebla, Pue., MEXICO