Registered: Jan 2004
Posts: 350

Why do totalistic cellular automata have symmetric behavior? The explanation given on page 61 in the NKS book is: “The symmetry of the patterns is a consequence of the basic structure of totalistic rules.”

But what is this basic structure? Well for one thing the rules consist of a list of base three digits, whereas the elementary rules consist of binary digits. And since there are only 2187 three color totalistic rules it only takes seven digits to represent the rule compared to the eight digits required for the elementary rules.

However, this difference in the structure of the rules is not what accounts for the symmetry. Rather it is the way the neighborhood produces the pointer for selecting the digit from the rule.

For the totalistic rules the pointer is formed by taking the average of the cell values in the neighborhood. That average turns out to be equal to one of the seven possible place values associated with the list of digits in the totalistic rule. The updated cell value is then the digit corresponding to the place value.

But with the elementary rules the values of the cells form a list that is converted to a decimal integer which points to the place in the rule’s list of binary digits. It is this digit that is copied into the updated cell location.

How is it then that this difference in procedures for selecting the updated cell value explains the symmetry characteristic of the totalistic cellular automata?

Well, taking the average of cells yields the same result for the left and right halves of the cellular automaton because the cells have the same content on the left and right sides. It can’t be any other way because the initial conditions are a single black cell at the center.

Compare this with the elementary cellular automata. The content of a neighborhood of cells is not averaged. Rather the values are taken as a list that is converted to decimal and used as a pointer into the list of digits in the rule.

Now a pointer thus formed from cells beginning at the center and extending to the left will be a reflection of the values of cells on the right. Some of the time the pointer values thus formed will not be the same. So the elementary cellular automaton will not always have symmetrical behavior.

There are other ways to get symmetrical behavior similar to that characteristic of totalistic rules. One way is to set up rules as lists of any integers of a certain length and to then have the neighborhoods total the values of cells modulo that length. The result will always be pointing to one of the integers in the rule. That integer is then copied to the cell as its updated value.

When the output of such a cellular automaton is graphed, it does not matter that the integers are not constrained to {0, 1} as in the elementary cellular automata or {0, 1, 2} as in the totalistic cellular automata. They can range as disparately as you like. However, they will always be from the list of integers selected when forming the rule.

For example, let the list of integers be these eight base ten digits: {1, 59, 43, 7, 13, 85, 64, 28}. And let the cell and its neighbors be these initial digits:{0, 0, 1}. The sum modulo the length of the list of integers in the rule is then: Mod[{0, 0, 1}, 8] = 1. Pointing into the list of digits in the rule starting with the right digit numbered digit 0, this gives an updated cell value of 64.

Before long the values of the cell and its neighbors are all digits taken from the rule instead of the digits in the initial conditions. However, whatever the values of the cell and its neighbors, their sum modulo the length of the list of integers in the rule always points to one of the integers in the rule as the updated cell value.

So the rule itself, the list of digits, plays a passive role in the update process. It just provides a source for the cell’s updated value. But it does not select it. Rather it is the mechanism at the neighborhood that generates a pointer that is used to select the update value from the pool of digits in the rule.

This is true whether the mechanism for creating the pointer uses a convert to decimal technique as with the elementary rules, an averaging technique as with the totalistic rules, or a modulo technique as with this example. And other techniques might be employed such as selecting at random after applying some weighting scheme with respect to the cell and its neighbors.

What is the significance of such distinctions? Well it helps mold inquiry into applications of cellular automata and research that seeks to discover the computations behind natural processes. For instance, we speak of the gene pool rather than a genetic rule.

Here is sample code for selecting a pointer into a pool of eight integers that makes up a rule:

makePointer[rulePool_, neighborhood_] := Reverse[rulePool] [[ Mod[Apply[Plus, neighborhood], 8] +1 ]]

Attached are sample graphics of cellular automata that employ this modulo mechanism. Each was executed with the same initial conditions: a single 1 centered on a line of 255 0s. The neighborhood consists of the cell and its two adjacent neighbors. The cellular automata ran for 128 steps.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 12-20-2005 at 07:44 PM

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

The short answer for the symmetry of the totalistic rules is that when a rule is symmetric abut the center cell, then it preserves any flip symmetry.

Symbolically, write -s for the flip of s about the center cell. If a CA rule f[x1,x2,x3] satisfies f[x1,x2,x3]==f[x3,x2,x1] then the time step F satisfies F[-s]==-F[s].

It is easy to verify, e.g., flipping x_1,x_2,x_3 gives the sequence x_3,x_2,x_1 at positions -3,-2,-1, respectively. The updated value at position -2 is then f[x_3,x_2,x_1] which by assumption is the same as f[x_1,x_2,x_3].

Totalistic rules are symmetric, but there are other symmetric rules which are not totalistic.

The other thing you mentioned is interesting, if I understand it right, the rule depends only on the values of the integers modulo 8, so they are totalistic rules with 8 colors.

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

I prefer your short answer. And yes, these are eight color graphs. But I don’t think you understood the point about mod 8.

As can be seen in the attached graphic, replacing each of the cell values with a mod 8 value results in a different display. Obviously two different cell values can sometimes have the same mod 8 value. And when this happens, the differentiation in the graph is lost.

But this is not what occurs in the original set of graphs. Rather the values of the cells are not mod 8. It is the pointer into the list of values in the rule that is mod 8. This pointer is generated by Mod[Apply[Plus, neighborhood], 8] +1, as stated in the previous post.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged