[Nested box from rule 6 of one-neighbor CA] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1

Nested box from rule 6 of one-neighbor CA
(Click here to view the original thread with full colors/images)

Posted by: Tommaso Bolognesi

Nested box from rule 6 of one-neighbor CA

T. Bolognesi - ISTI-CNR
t.bolognesi@isti.cnr.it

This notebook discusses some aspects of the behaviour of the 16 cellular automata whose behaviour depends only on the (left) nearest-neighbor.

Of course, no universality is possible with such a simple model of computation, but nested behaviour can indeed be achieved: rule 6, and its complementary rule 9, when started with a simple initial array of bits, such as {1,0,0,...,0}, yields a nested tree structure which appears as a rotation of the well known pattern for rule 90 of the (2-neighbor) elementary cellular automata (NKS book, p. 25, bottom figure). Note that Rule 6 implements the exclusive OR (XOR) function; it resembles a derivative, with bit 0 detecting two equal bits, and bit 1 detecting two different bits up in the previous line.

One cute aspect of rule 6 is that it is invariant w.r.t. swapping the vertical and horizontal dimensions (time and space). In other words, the 4 small, three-bit diagrams describing this rule appear the same when reading them top to bottom or right to left.

By using rule 6 with random inital row of length 2**n, one always gets a behaviour satisfying the following properties (proofs are simple and omitted).

1.
Any cell in the pattern is the result of applying the XOR function not only to its immediate north and north-west predecessors, as required by rule 6, but also to any pair of predecessors found at vertical distance 2**k (going those two directions).

2.
As a consequence of fact 1, line 2**(n-1)+1 has form a.a, that is, t is the concatenation of two equal bit tuples of length 2**(n-1).

3.
As a consequence of facts 1 and 2, line 2**n + 1 is all white. This is a fixed point of the process. Thus, all activity terminates within the square region of size 2**n.

4.
The square has nested structure, in the sense that if one consider it as composed by two upper and two lower squares, then the lower squares turn out to be identical, and recursively structured as the whole square:

A B
C C

5.
Every column, of length 2**n, preserves all the information of the initial row; the latter can be easily reconstructed, in light of the above mentioned time-space symmetry, by using the column as initial condition, and by developing a triangle of bits, reading the 4 three-bit patterns of rule 6 from right to left, rather than from top to bottom.

6.
The reversibilty between the first line and the last (or, in fact, generic) column of the square implies that the bottom black line has exactly probability 1/2 to appear as last line of the square, that is, as line 2**n, thus giving a nice full square as shown above. In the remaining half of the cases, the closing line appears earlier (because of fact 3 above).

The potential interest for the 'random' box above might derive from the fact that the completely random inital configuration evolves in a random-like fashion for a time with definite upper bound, and closely approximates the latter with high probability. On the other hand, when using random initial conditions of size other than a power of two (but possibly close to it), periodic sequences with quasi-periodic substructures are obtained, of some possible visual /'musical' interest.

Posted by: Tommaso Bolognesi

By exploring the 256 standard CA rules involving two nearest neighbors, using random inputs of length 2**n, and wrapping (that is, applying rules in circular fashion), one notices that rule 60 exhibits the same sudden-death phenomenon observed for rule 6 of one-neighbor elementary CA's, discussed above. That is, it yields a finite behaviour of length at most 2**n with nested box structure, the upper bound being reached with probability 1/2.

The reason is that rule 60 actually cares only about the first two cells (itself and its left neighbor) out of three, and yields the exclusive OR between them, as done by the one-neighbor rule 6.

Similarly, rule 102 for two-neighbor automata computes the XOR of the last two cells, while ignoring the first one, and yields the same type of terminating behaviour.

Posted by: Jason Cawley

Some nice results...

Note that one can consider these rules as ECAs. Sure, they are simpler, in that the right neighbor does not matter. But there are ECAs for which the right bit does not matter.

They are exactly those whose integer digits in base two are symmetric, with the first half (4) exactly the same as their second half. Having the same first and second half of the rule table, is equivalent to the rightmost bit not mattering, aka it being a "don't care" bit.

Thus rule 6 in the 2 neighbor case is rule 102 in the standard ECA (as you basically say in your second post) -

FromDigits[{0,1,1,0},2] = 6
FromDigits[{0,1,1,0,0,1,1,0},2] = 102

The colors flipped version - corresponding to your rule 9 - is rule 153.

If you use the built in CellularAutomaton function in Mathematica, you can immediately see the results are the same. Thus I appended to your existing notebook the 5.1 function call -

ArrayPlot[CellularAutomaton[102, myInitList, 127]]

- using your set variable value for myInitList, and the resulting picture is exactly the same as your rule 6.

60 is among the 16 because it's digits are {0,0,1,1,1,1,0,0}, again symmetric, first half the same as second half. So the rightmost is a "don't care" bit.

There is also a nice correspondance of that rule 102 aka your rule 6 to the following -

ArrayPlot[Mod[Array[Binomial, {16, 16}, 0], 2]]]

Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings