12 views

Skip to first unread message

Jul 26, 1994, 10:29:28 PM7/26/94

to c...@think.com

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu