TAOCP 7.2.2.2 Exercise 116

Exercise 116. [22] [22] Find examples of Life flipflops for which $N$ and $N'$ are tomographically equal.

Verified: yes
Solve time: 4m03s

The original argument fails at the point where it assumes a non-symmetry (column swapping) preserves the Game of Life evolution. A correct construction must ensure that both configurations are genuine period-2 Life evolutions, without relying on any transformation that is not a symmetry of the dynamics.

A standard way to repair the idea is to encode a purely combinatorial “tomographic swap” at a coarse scale, using disjoint copies of a fixed period-2 oscillator.

1. A fixed period-2 gadget with isolation

Let $O$ be any finite Life oscillator of period $2$ (for example a beacon). It satisfies

$$ O(t+2) = O(t), \quad O(t+1) \neq O(t). $$

Fix a sufficiently large integer $L$ such that:

all live cells of $O$ are contained in a square $Q$,
and any two translates of $Q$ separated by at least $L$ cells do not interact for all time, by the standard finite propagation speed of Life (no information travels faster than one cell per generation in the Moore neighborhood).

We then treat each translate of $Q$ as a “macro-cell” containing either a copy of $O$ or being empty.

2. Macro-configurations and decoding

Consider a finite set of macro-cells indexed by pairs $(i,j)$ in a grid.

To each macro-cell we assign either:

$O$, placed entirely inside the corresponding translated square, or
the empty configuration.

Let $E(i,j)\in{0,1}$ encode this choice.

Because of the separation condition, the global configuration evolves as a disjoint union of independent copies of $O$. Hence:

every occupied macro-cell evolves with period $2$,
empty cells remain empty,
therefore the entire configuration is a flipflop (period $2$).

Thus any $0$-$1$ matrix $E$ produces a valid Life flipflop.

3. Construction of two distinct configurations

We now construct two different macro-patterns with identical row and column sums.

Let the macro-grid consist of four positions:

$$ (1,1), (1,2), (2,1), (2,2). $$

Define two incidence matrices:

$$ E = \begin{pmatrix} 1 & 0 \ 0 & 1 \end{pmatrix}, \qquad E' = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix}. $$

These satisfy:

row sums: $(1,1)$ for both $E$ and $E'$,
column sums: $(1,1)$ for both $E$ and $E'$,
but $E \neq E'$.

4. Lifting to Life configurations

Define $N$ as the Life configuration obtained by placing a copy of $O$ in each macro-cell where $E(i,j)=1$, and empty space elsewhere.

Define $N'$ analogously using $E'$.

By construction:

all copies of $O$ are separated by distance at least $L$,
hence they do not interact,
hence both $N$ and $N'$ evolve as independent unions of period-2 oscillators,
therefore both $N$ and $N'$ are flipflops.

5. Tomographic equality

Row sums

Each occupied macro-cell contributes the same fixed number $r$ of live cells to each row of its macro-square.

Thus the total row sum in a given macro-row is:

$$ r \cdot (\text{number of occupied macro-cells in that row}). $$

Since $E$ and $E'$ have identical row sums, the induced fine-level row sums in $N$ and $N'$ are identical.

Column sums

Similarly, each occupied macro-cell contributes a fixed column pattern determined by $O$, and scaling by the number of occupied macro-cells in each macro-column gives:

$$ \text{column sum} = r' \cdot (\text{macro-column count}). $$

Since $E$ and $E'$ have identical column sums, the induced column sums in $N$ and $N'$ agree.

6. Distinctness

Because $E \neq E'$, there exists at least one macro-cell where one configuration contains $O$ and the other is empty. Hence:

$$ N \neq N'. $$

7. Conclusion

We have constructed two finite Life flipflops $N$ and $N'$ such that:

both are unions of disjoint period-2 oscillators, hence both have period $2$,
they differ as configurations,
they have identical row sums and column sums because they arise from incidence matrices with equal tomographic data,
and the construction uses only legitimate Life dynamics without any non-symmetry transformation.

Thus there exist Life flipflops $N, N'$ that are tomographically equal. ∎