Notes

Chapter 6: Starting from Randomness

Section 6: Special Initial Conditions


Self-similarity of additive [cellular automaton] rules

The fact that rule 90 can emulate itself can be seen fairly easily from a symbolic description of the rule. Given three cells {a1, a2, a3} the rule specifies that the new value of the center cell will be Mod[a1 + a3, 2]. But given {a1, 0, a2, 0, a3, 0} the value after one step is {Mod[a1 + a2, 2], 0, Mod[a2 + a3, 2], 0} and after two steps is again {Mod[a1 + a3, 2], 0}. It turns out that this argument generalizes (by interspersing k-1 0's and going for k steps) to any additive rule based on reduction modulo k (see page 952) so long as k is prime. And it follows that in this case the pattern generated after a certain number of steps from a single non-white cell will always be the same as one gets by going k times that number of steps and then keeping only every k^th row and column. And this immediately implies that the pattern must always have a nested form. If k is not prime the pattern is no longer strictly invariant with respect to keeping only every k^th row and column—but is in effect still a superposition of patterns with this property for factors of k. (Compare page 870.)


From Stephen Wolfram: A New Kind of Science [citation]