Elementary cellular automaton showing eventually periodic behavior after large number of iterations.

Question

In this video:

Cellular Automata and Rule 30

Stephen Wolfram talks about such an elementary cellular automaton at 17:01. Does anybody have an idea which one exactly he could be talking about?

Answer 1

There are more details — quite a lot more details — in the original Announcing the Rule 30 Prizes post on Stephen Wolfram's blog. In particular, the specific rule is named there:

Here’s a somewhat funky example—found by a search—of a rule with 4 possible colors (totalistic code 150898). Run it for 200 steps, and the center column looks quite random:
[Image 1]
After 500 steps, the whole pattern still looks quite random:
[Image 2]
But if one zooms in around the center column, there’s something surprising: after 251 steps, the center column seems to evolve to a fixed value (or at least it’s fixed for more than a million steps):
[Image 3]

As it turns out, the Mathematica code to generate the images (and thus simulate the rule) is also hidden on the blog post; selecting and copy-pasting the first image on the page, for example, yields the following code snippet:

ArrayPlot[
 CellularAutomaton[{150898, {4, 1}, 1}, {{1}, 0}, {200, 150 {-1, 1}}],
  ColorRules -> {0 -> Hue[0.12, 1, 1], 1 -> Hue[0, 0.73, 0.92], 
   2 -> Hue[0.13, 0.5, 1], 3 -> Hue[0.17, 0, 1]}, 
 PixelConstrained -> 2, Frame -> False]

If you'd rather not just try to figure out what that code does, I believe ANKoS page 60 (annoyingly, the blog post links to page 61) describes Wolfram's convention for numbering 1D totalistic CA rules and how to decode and simulate them. Specifically:

1. Write out the rule number in base $n$ with $w(n-1)+1$ digits, where $n$ is the number of states and $w$ is the width of the neighborhood (here apparently taken to be 3 by default). For example, 150898 written in base 4 with 10 digits is 0210311302₄.
2. To apply the CA rule, replace the state of each cell (numbered from 0 to $n-1$) with the $k$-th digit from the right in the base $n$ rule number (counting from zero, i.e. the rightmost digit is numbered 0 and the leftmost is numbered $w(n-1)$), where $k$ is the sum of the states of all $w$ cells in this cell's neighborhood (including the cell itself).

Just to confirm that decoding and applying the rule like this indeed yields output matching the images in the blog post, here's a simple Python program to simulate this rule on a finite wrap-around lattice:

rule = 150898
states = 4
width = 3

# decode rule number
table = tuple((rule // states**k) % states for k in range(width*(states-1)+1))

# initial cell states
cells = ((0,) * 20) + (1,) + ((0,) * 20)

# transition function
def new_state(i):
    neighbors = (cells[(i + j - width // 2) % len(cells)] for j in range(width))
    return table[sum(neighbors)]

for t in range(20):
    print("".join(str(s) for s in cells))
    cells = tuple(new_state(i) for i in range(len(cells)))

Try it online!

Simulating this rule on a sufficiently wide lattice, starting from a single 1 cell on a background of 0 cells, one can observe that the center cell indeed eventually gets stuck in state 1 while its neighbors alternate quasi-randomly between states 1 and 3. Indeed, examining the base-4 rule code, it's not too hard to see why this particular configuration at the center of a symmetric pattern is invariant under the rule:

• As a totalistic rule, the state transition function is necessarily left/right mirror symmetric. Thus, the time evolution of any mirror symmetric initial pattern necessarily remains symmetric. In particular, this implies that the two neighbors of the center cell will always have the same state.
• If the center cell is in state 1, and both of its neighbors in state 1 or 3, then the sum of the center cell's neighborhood states is either 1+1+1 = 3 or 3+1+3 = 7. Looking at the base-4 rule code, we can see that digits 3 and 7 (counting right-to-left from zero) are both 1.
• Also, if a cell is in state 1 or 3, and one of its neighbors is in state 1, then the sum of its neighborhood states must be between 1+1+0 = 2 and 1+3+3 = 7 inclusive. Looking again at the base-4 rule code, we can see that, out of digits 2–7, almost all are either 1 or 3. The one exception is digit 6, which is 0; the only way this sum can arise under these constraints is as 1+3+2 = 6, i.e. if the cell itself is in state 3 and its other neighbor is in state 2.
• A little bit more examination of the rule string, however, shows that there is no possible configuration of four cells of the form "$1xyz$", where $x \in \{1,3\}$, that could give rise to the configuration "$32$" for its two middle cells on the next time step. Specifically, for the left middle cell to become 3, $1+x+y$ must be either 2 or 5. Thus, either $x = 1$ and $y = 0$, $x = 1$ and $y = 3$, or $x = 3$ and $y = 1$. In the first case, $1 \le x+y+z \le 4$; in the latter two, $4 \le x+y+z \le 7$. But for the right middle cell to become 2, $x+y+z$ must be either 0 or 8, which is impossible.

Thus, once the five center columns of a centrally symmetric pattern under this rule end up in the configuration "$a111a$" or "$b313b$", where $a$ is any state and $b$ is any state other than 2, they cannot ever again enter any configuration not of this kind.