Complexity_ A Guided Tour - Melanie Mitchell [68]
How does a lightbulb “decide” whether to turn on or off at each time step? Each bulb follows a rule that is a function of the states in its neighborhood—that is, its own state (i.e., on or off) and those of the eight neighbors to which it is connected.
For example, let’s say that the rule followed by each lightbulb is, “If the majority of bulbs in my neighborhood (including myself) are on, turn on (or stay on, if already on), otherwise turn off (or stay off, if already off).” That is, for each neighborhood of nine bulbs, if five or more of them are on, then the middle one is on at the next time step. Let’s look at what the lightbulb grid does after one time step.
FIGURE 10.2. Left: The same array of lightbulbs as in figure 10.1, set up in an initial configuration of on and off states. Connections between lightbulbs are not shown. Right: each bulb’s state has been updated according to the rule “take on whichever state is a majority in my local neighborhood.”
As explained in the caption to figure 10.1, to make sure that each lightbulb indeed has eight neighbors, we will give the grid circular boundaries. Imagine that the top edge is folded over and touches the bottom edge, and the left edge is folded over and touches the right edge, forming a donut shape. This gives every lightbulb eight neighbors.
Now let’s go back to the rule defined above. Figure 10.2 shows the initial grid and its configuration after following the rule for one time step.
I could have defined a more complicated rule, such as, “If at least two but no more than seven bulbs in my neighborhood are on, then turn on, otherwise turn off,” and the updated grid would have looked different. Or “if exactly one bulb is off or exactly four bulbs are on in my neighborhood, turn off, otherwise turn on.” There are lots of possibilities.
Exactly how many possible different rules could be defined? “Lots” is really understating it. The answer is “two raised to the power 512” (2512), a huge number, many times larger than the number of atoms in the universe. (See the notes to find out how this answer was derived.)
This grid of lightbulbs is a cellular automaton. More generally, a cellular automaton is a grid (or lattice)of cells, where a cell is a simple unit that turns on or off in response to the states in its local neighborhood. (In general, cells can be defined with any number of states, but here we’ll just talk about the on/off kind.) A cellular automaton rule—also called a cell update rule—is simply the identical rule followed by each cell, which tells the cell what its state should be at the next time step as a function of the current states in its local neighborhood.
Why do I say that such a simple system is an idealized model of a complex system? Like complex systems in nature, cellular automata are composed of large numbers of simple components (i.e., cells), with no central controller, each of which communicates with only a small fraction of the other components. Moreover, cellular automata can exhibit very complex behavior that is difficult or impossible to predict from the cell update rule.
Cellular automata were invented—like so many other good ideas—by John von Neumann, back in the 1940s, based on a suggestion by his colleague, the mathematician Stan Ulam. (This is a great irony of computer science, since cellular automata are often referred to as non -von-Neumann-style architectures, to contrast with the von-Neumann-style architectures that von Neumann also invented.) As I described in chapter 8, von Neumann was trying to formalize the logic of self-reproduction in machines, and he chose cellular automata as a way to approach