Eigenvalues.

Again there are two ancestors per state, giving squares of 4 and the minimal element count of 8 for N. This time and are idempotents with eigenvalues 0 and 1 but they do not commute. N is nevertheless ``idempotent'' according to ; its element sum is 8 with powers growing at the minimal rate.

The difference is that Rule 12 is reversible, via a left shift, whereas Rule 6 is not reversible at all, each different value of a boundary cell resulting in a completely different ancestor (or no ancestor at all if the left and right boundaries conflict). Rule 12 is indifferent to its right boundary, but the ancestor is uniquely determined by the left boundary. Yet both rules are surjective.

Both these rules have a pair matrix with eight 1's, the minimal number possible; uniformly distributed throughout the rows and columns for Rule 6, but not for Rule 12. The difference is crucial, and is related to the observation that rules of the Fredkin type are all constructed from groups of variables, some of which are superfluous. Right shift does not depend upon the right cell, so the matrices (and their tensor squares) have constant rows, bunching the 1's in a way that does not occur for Rule 6.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx