A cellular automaton is a formalism that’s sometimes used to model complex systems—like the spatial distribution of populations, for example. Here is the model, in its simplest form. We start from an...

A cellular automaton is a formalism that’s sometimes used to model complex systems—like the spatial distribution of populations, for example. Here is the model, in its simplest form. We start from an n-by-n toroidal lattice of cells: a two-dimensional grid, that “wraps around” so that that there’s no edge. (Think of a donut.) Each cell is connected to its eight immediate neighbors

Cellular automata are a model of evolution over time: our model will proceed in a sequence of time steps. At every time step, each cell u is in one of two states: active or inactive. A cell’s state may change from time t to time t + 1. More precisely, each cell u has an update rule that describes u’s state at time t + 1 given the state of u and each of u’s neighbors at time t. (For example, see Figure 9.28.)

Let’s call an update rule a strictly cardinal update rule if—as in the Game of Life—the state of a cell u at time t + 1 depends only the following: (i) the state of cell u at time t, and (ii) the number of active neighbors of cell u at time t. How many different strictly cardinal update rules are there?