Reading the Rule

Every other puzzle in this book is handed a rule and asked for an arrangement. This one runs the other way. We are shown two photographs of a row of cells, one a moment after the other, and asked for the rule that turned the first into the second. It is an inverse problem, the kind a scientist faces with the world: not to work out what a known law produces, but to read the law off what it has already produced.

A line that ticks

The setting is a one-dimensional cellular automaton, the simplest thing that can be said to compute. A row of cells, each black or white, ticks forward in steps. At each step every cell looks at itself and its two neighbours, three cells in all, and turns black or white according to a fixed rule. Three cells, each two ways, make eight possible neighbourhoods, and the rule is just a verdict, black or white, for each of the eight. So a rule is eight bits, and there are $2^8 = 256$ of them, the family Wolfram numbered $0$ to $255$.

Number the eight neighbourhoods by reading them as binary, the left neighbour worth $4$, the cell itself $2$, the right neighbour $1$. Then a neighbourhood is a number $c \in \{0, \dots, 7\}$, and the rule is a bit $r_c$ for each, the cell’s next colour. The rule’s own number is $\sum_c r_c \, 2^c$.

The inference

Let $s$ be the first row and $s'$ the second, with cells off the ends read as white. For a cell $j$ its neighbourhood number is the constant $$c_j = 4\, s_{j-1} + 2\, s_j + s_{j+1},$$ and whatever rule produced the second row must answer that neighbourhood with the colour actually seen there. So each observed cell pins one bit of the rule: $$r_{c_j} = s'_j \qquad (\text{for each observed cell } j).$$ The unknowns are the eight bits $r_0, \dots, r_7$; the constraints read them off the data. If the row is long enough that all eight neighbourhoods appear, every bit is pinned and the rule is known; where a neighbourhood never occurs, its bit is free, and more than one rule fits.

from ortools.sat.python import cp_model

def neighbourhood(s, j):
    a = s[j - 1] if j > 0 else 0
    b = s[j]
    c = s[j + 1] if j + 1 < len(s) else 0
    return 4 * a + 2 * b + c

def infer_rules(s1, s2, cells):
    m = cp_model.CpModel()
    r = [m.NewBoolVar("") for _ in range(8)]
    for j in cells:
        m.Add(r[neighbourhood(s1, j)] == s2[j])
    rules = []

    class Collect(cp_model.CpSolverSolutionCallback):
        def __init__(self):
            cp_model.CpSolverSolutionCallback.__init__(self)

        def on_solution_callback(self):
            rules.append(sum(self.Value(r[k]) << k
                             for k in range(8)))

    s = cp_model.CpSolver()
    s.parameters.enumerate_all_solutions = True
    s.Solve(m, Collect())
    return sorted(rules)

Here are the two rows, black for one and white for zero: $$\begin{array}{cccccccccc} \square & \square & \square & \blacksquare & \square & \blacksquare & \blacksquare & \blacksquare & \square & \square \\ \square & \square & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \square & \blacksquare & \square & \square \end{array}$$ Across the eight inner cells the neighbourhoods come out as $0, 1, 2, 5, 3, 7, 6, 4$, all eight of them once each, so every bit of the rule is fixed. The solver returns one rule and no other: number $110$, the bits $01101110$ read from $r_7$ down to $r_0$. That is the rule Wolfram showed can compute anything a computer can, recovered here from a single tick of ten cells.

When the data is not enough

Now suppose we had seen less, only the cells whose neighbourhoods were among the first four, $0$ to $3$. Those fix the four low bits of the rule and say nothing about the rest, so the four high bits are free and $$2^4 = 16$$ rules account for everything observed, rule $110$ among them. The solver, asked the same question of the smaller evidence, returns all sixteen. This is the article’s quiet point, and it is the scientist’s predicament in miniature: when several laws fit the data equally, no amount of staring at what you have will choose between them. Only a fresh observation, a neighbourhood not yet seen, can rule a candidate out. The model does not hide the ambiguity or pick a favourite; it reports the whole set of survivors, which is the honest answer.

Sources. The cellular-automaton rule-inference model is from Martin J. Chlond, A New Kind of IP, INFORMS Transactions on Education volume $4$, number $2$ ($2004$), pages $49$–$50$, whose title puns on Stephen Wolfram’s A New Kind of Science (Wolfram Media, $2002$), the source of the rule numbering and of the result that rule $110$ is computationally universal. Chlond infers rule $30$ from generated data and notes, as here, that partial data may leave several rules consistent; the ten-cell instance, its unique rule $110$, and the sixteen-rule partial reading are the present chapter’s own, each produced and checked by the model above. The one-dimensional automaton and its notation are Wolfram’s; the best-known two-dimensional example, Conway’s Game of Life, is older, from $1970$.