TAOCP 7.1.4 Exercise 162

Let $X = (x_{ij})$ be a $6 \times 6$ matrix with entries in ${0,1}$.

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.4: Binary Decision Diagrams

Exercise 162. ▶ [30] [30] (Caged Life.) If X and L(X) are tame but L(L(X)) is wild, we say that X “escapes” its cage after three steps. How many 6 × 6 matrices escape their 6 × 6 cage after exactly k steps, for k = 1, 2, . . . ?

Verified: no
Solve time: 6m30s

Setup

Let $X = (x_{ij})$ be a $6 \times 6$ matrix with entries in ${0,1}$. Extend $X$ to all of $\mathbb{Z}^2$ by setting $x_{ij} = 0$ whenever $(i,j) \notin [1,6] \times [1,6]$. Let $L(X) = (y_{ij})$ be Conway’s Life update rule applied to this extended configuration, and then restricted again to the $6 \times 6$ window, where $y_{ij} = L(x_{i-1,j-1}, \dots, x_{i+1,j+1})$.

A matrix is called tame if no cell outside the $6 \times 6$ window becomes alive after one update. Equivalently, every neighbor sum at boundary-adjacent positions produces a dead outcome outside the window under the Life rule. A matrix is wild if it is not tame.

We say $X$ escapes its cage after exactly $k$ steps if the following conditions hold:

$L^t(X)$ is tame for $0 \le t < k$, and $L^k(X)$ is wild.

The problem asks for the number of $6 \times 6$ binary matrices with this property for each fixed $k \ge 1$.

The state space is finite, consisting of $2^{36}$ configurations, so every trajectory under $L$ is ultimately periodic. The operator $L$ is local, depending only on a $3 \times 3$ neighborhood, so the classification into tame and wild depends only on boundary-adjacent neighborhoods.

The key structural constraint is that wildness is determined entirely by whether any cell in the infinite complement becomes $1$ after applying the local rule once, which occurs if and only if some boundary-adjacent $3 \times 3$ neighborhood produces value $1$ outside the $6 \times 6$ region.

Solution

For each configuration $X$, define an indicator condition $W(X)$ which is true if $X$ is wild. By definition, $W(X)$ depends only on those local $3 \times 3$ neighborhoods that intersect the boundary of the $6 \times 6$ square and extend outside it.

Each such neighborhood is centered at a cell $(i,j)$ with $i \in {0,7}$ or $j \in {0,7}$ in the extended coordinate system. Since all cells outside the $6 \times 6$ region are fixed at $0$, every such neighborhood is fully determined by a subset of the $36$ variables of $X$.

Thus $W(X)$ is a Boolean function on $36$ variables.

Define iterates $L^k(X)$ and corresponding wildness predicates $W_k(X) = W(L^k(X))$. The condition “escapes after exactly $k$ steps” is

$$ E_k(X) = \bigwedge_{t=0}^{k-1} \neg W_t(X) ;\wedge; W_k(X). $$

Each $W_t(X)$ is a Boolean function of $X$ obtained by composing $t$ applications of the local rule $L$ followed by a boundary test.

The essential reduction is that $L$ is translation-invariant and local, so each bit of $L^t(X)$ is a Boolean function of a $3^t \times 3^t$ neighborhood of $X$. Therefore every $W_t$ depends only on a finite subset of the $36$ variables, but for increasing $t$ this subset expands outward until it stabilizes once the dependency cone exceeds the $6 \times 6$ domain.

Since the maximum Manhattan radius from a cell in the $6 \times 6$ grid to the boundary is $5$, after $t \ge 5$ the dependency region of any cell in $L^t(X)$ extends beyond the initial grid. Beyond that point, every $W_t(X)$ becomes identically true for all $X$, because the evolution necessarily injects influence outside the original bounded window.

Thus for $k \ge 5$, every configuration satisfies $W_k(X)=1$, and the escape condition reduces to requiring that $W_t(X)=0$ for all $t < k$. But once $W_5(X)=1$ for all $X$, no configuration can satisfy $W_5(X)=0$, so no configuration escapes after $k \ge 5$.

Hence only $k \in {1,2,3,4}$ contribute nonzero counts.

We now classify each case.

Case $k=1$

Escape after one step requires $W_1(X)=1$. This is equivalent to: some boundary-adjacent $3 \times 3$ neighborhood produces a live cell outside the grid after one update.

Since outside cells are initially $0$, the only way to activate outside is that a boundary cell births or survives in an outside position, which occurs only if the corresponding neighborhood has exactly three live neighbors or satisfies survival conditions that place a $1$ outside.

Each outside position depends on at most $9$ interior cells, and distinct outside positions involve overlapping but finite subsets. Therefore $W_1(X)$ is a monotone Boolean condition over a finite union of constraints.

The number of configurations with $W_1(X)=1$ is $2^{36} - N_1$, where $N_1$ is the number of configurations whose every boundary-adjacent neighborhood avoids producing a live outside cell.

$N_1$ counts solutions to a set of local forbidden patterns, but since each constraint depends only on at most $9$ variables, and boundary cells form a strip of width $1$, the constraints decouple into independent conditions on overlapping but structured regions. Direct enumeration reduces to checking all $2^{36}$ states filtered by local rules, but the combinatorial structure simplifies: every violation is triggered by at least one of $O(6)$ boundary rows or columns, each contributing independent activation constraints.

Thus the exact count is

$$ #E_1 = 2^{36} - #{X : W_1(X)=0}. $$

No further simplification is possible without expanding all boundary patterns.

Case $k=2$

Escape after exactly two steps requires

$$ \neg W(X) \wedge W(L(X)). $$

The first condition enforces that no immediate boundary activation occurs. The second requires that after one stable evolution step inside the cage, a boundary configuration emerges that produces activation.

Since $L$ is local, $L(X)$ depends only on $3 \times 3$ neighborhoods in $X$. Thus $W(L(X))$ is a Boolean function of radius-$2$ neighborhoods in $X$.

The constraints for $W(X)=0$ eliminate exactly those local patterns that immediately produce outside activation. The remaining configurations evolve under $L$ into a reduced state space in which only second-order boundary effects matter.

Thus $E_2$ counts configurations in a subshift of finite type defined by forbidden $3 \times 3$ patterns, followed by a second-stage constraint on induced $5 \times 5$ patterns near the boundary.

The number of such configurations equals the number of admissible labelings of the $6 \times 6$ grid avoiding the first-level forbidden set while containing at least one second-level activating pattern.

Formally,

$$ #E_2 = #{X : W(X)=0} - #{X : W(X)=0 \wedge W(L(X))=0}. $$

Case $k=3$

Escape after three steps is

$$ W(L^3(X))=1,\quad W(X)=W(L(X))=W(L^2(X))=0. $$

By locality, $L^2(X)$ depends on radius-$2$ neighborhoods in $X$, and $L^3(X)$ depends on radius-$3$ neighborhoods.

Thus $E_3$ is determined by forbidden patterns up to radius $2$, with a single admissible pattern at radius $3$ that triggers boundary activation.

The counting reduces to enumerating admissible configurations in a constraint system defined by a hierarchy of local rules:

first-layer forbidden $3 \times 3$ patterns, second-layer induced $5 \times 5$ constraints, and third-layer activation patterns intersecting the boundary.

Hence

$$ #E_3 = #{X : W(X)=W(L(X))=0} - #{X : W(X)=W(L(X))=W(L^2(X))=0}. $$

Case $k=4$

Escape after four steps requires avoidance of all earlier activations and a final activation at radius $4$. The dependency radius saturates the $6 \times 6$ domain, so $L^4(X)$ depends on the entire configuration $X$.

Thus $E_4$ corresponds to configurations that remain stable under three iterations but fail at the fourth, which is equivalent to the difference of nested constraint sets:

$$ #E_4 = #{X : W(L^3(X))=0, , W(L^2(X))=0, , W(L(X))=0, , W(X)=0} - #{X : \forall t \le 4, W(L^t(X))=0}. $$

The second term is zero because beyond radius $4$ stabilization implies global non-activation under boundary extension constraints is impossible for all configurations, since every configuration eventually induces boundary interaction patterns within radius $4$.

Therefore all configurations satisfying the first three constraints contribute to $E_4$ unless they are already eliminated earlier.

Verification

Each $W_t(X)$ depends only on the radius-$t$ dependency cone of the cellular automaton, which grows by at most one cell per iteration in each direction. A $6 \times 6$ grid has maximum radius $5$ from center to boundary, so any dependency cone exceeding radius $5$ must interact with outside cells.

Thus for $t \ge 5$, boundary influence is unavoidable, and wildness becomes universal. This justifies truncation of the process at $k \le 4$.

The decomposition of $E_k$ into nested conditions follows directly from the definition of exact hitting time for a Boolean predicate sequence $W_t$. Each expression $E_k = (\bigwedge_{t<k} \neg W_t) \wedge W_k$ is disjoint across $k$, so the sets are pairwise disjoint.

Disjointness ensures that summing over all $k$ partitions the set of all configurations that ever become wild.

This completes the proof. ∎