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.)

An update rule is a function that takes the state of a cell and the state of its eight neighbors as input, and produces the new state of the cell as output. How many different update rules are there?