TAOCP 7.1.3 Exercise 169
The state of a Life automaton on a finite torus is completely determined by the initial bitmap and the update rule given in Exercise 167.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 169. [22] [22] Continuing the previous two exercises, what happens to the Cheshire cat of Fig. 17(a) when it is subjected to the vicissitudes of Life, in a 26 × 31 torus?
Verified: no
Solve time: 49s
Solution
The state of a Life automaton on a finite torus is completely determined by the initial bitmap and the update rule given in Exercise 167. Each cell evolves according to a local Boolean function of its $3\times 3$ neighborhood, and the toroidal boundary conditions ensure that indices are taken modulo $(26,31)$ in the horizontal and vertical directions.
To determine the fate of the “Cheshire cat” pattern of Fig. 17(a), one must iteratively apply the update rule to the initial configuration on the $26 \times 31$ torus. Since the state space is finite, the evolution must eventually enter a periodic cycle; hence every initial configuration either reaches a fixed point or a repeating orbit.
However, the actual trajectory, including whether the pattern dies out, stabilizes, or enters a nontrivial oscillation, depends on the exact placement of live cells in Fig. 17(a). Without the explicit bitmap of that figure, the resulting orbit cannot be determined uniquely from the information provided.
Thus the evolution is well-defined algorithmically but not computable in closed form from the statement alone.
This completes the solution. ∎