How does On/Off Reversal work in Life-Like Cellular Automata

Question

I've recently been made aware of the concept of on-off rule reversal in life-like cellular automata. I understand the algorithm for calculating the rule reversal from a given rule. But I don't understand why the algorithm is the way that it is, or how it was derived. I also can't seem to find any explanations anywhere.

Answer 1

The transition rule of a Life-like cellular automaton (or, more generally, any two state outer-totalistic CA) can be regarded as a function $f$ that takes the current state $s$ of a cell (represented as $1$ = on and $0$ = off) and the number $n$ of cells in state $1$ its neighborhood and outputs the state $f(s, n)$ of the same cell (again, $1$ = on and $0$ = off) in the next generation.

For example, the transition rule of Conway's Game of Life (B3/S23) can be represented as the function $$f(s, n) = \begin{cases} 1 & \text{if $s = 0$ and $n = 3$,} \\ 1 & \text{if $s = 1$ and $n \in \{2,3\}$,} \\ 0 & \text{otherwise.} \\ \end{cases}$$

Given any such transition function $f$, we can define the transition function $f'$ of the corresponding state-reversed rule simply as $$f'(s, n) = 1 - f(1 - s, M - n),$$ where $M$ is the size of each cell's neighborhood (e.g. $M = 8$ for Life-like CA).

It should be easy to see that the function $f'$ is equivalent to $f$, except that we've simply swapped the state labels $0$ and $1$.

---

Conversely, given a transition function $f$, we can reconstruct the corresponding B/S rule string as follows:

• after "B", list all numbers $n \in \{0, \dots, M\}$ for which $f(0, n) = 1$; and
• after "S", list all numbers $n \in \{0, \dots, M\}$ for which $f(1, n) = 1$.

Now, applying the same construction to $f'$, we can see that:

• $f'(0, n) = 1$ if and only if $f(1, M-n) = 0$; and
• $f'(1, n) = 1$ if and only if $f(0, M-n) = 0$.

In other words, the rule string for the state-reversed rule represented by $f'$ will have:

• after "B", only those numbers $n$ for which $M-n$ does not appear after "S" in the original rule; and
• after "S", only those numbers $n$ for which $M-n$ does not appear after "B" in the original rule.