Flip Rules

These rules operate on an infinite grid of cells, where each cell (little square) is either black or white. Over time, the color of each cell may change from black to white or back to black, and the resulting pattern which changes over time is what we are interested in analyzing.

So how do these "Flip Rules" work?

Think of cells as a red&blue checkerboard in your mind. On alternate steps, update the red cells and the blue cells.

To update a cell, we'll flip it depending on how many of its four neighbors are black vs. white.

For example, one flip rule would be flip it if it has an odd number of neighbors of each color. ("Flip if Odd")

Another flip rule might be to flip it if all four neighbors are the same color. ("Flip if Uniform")

Another flip rule would be to flip it if it has two neighbors of each color. ("Flip if Balanced")

All of these rules are reversible, since each step is easily reversed.

Here are all the possible flip rules that treat black and white symmetrically:

                       Flip if

    all 4 the        all but one         two of
    same color       the same color      each color
       no                 no                no          "Never Flip"
       no                 no                yes         "Flip if Balanced"
       no                 yes               no          "Flip if Odd"
       no                 yes               yes         "Flip unless Uniform"
       yes                no                no          "Flip if Uniform"
       yes                no                yes         "Flip unless Odd"
       yes                yes               no          "Flip unless Balanced"
       yes                yes               yes         "Always Flip"

The "Never Flip" and "Always Flip" rules are clearly trivial; their future states can be predicted in constant time.

Let's consider the "Flip unless <condition>" rules. Each step is the same as doing "Flip if <condition>" followed by flipping everything. And flipping everything will not have any effect on the following step, since we are considering rules that are black/white symmetric! In fact, in two steps when we come back to this checkerboard, we'll flip them all again, so four steps of a "Flip unless <condition>" rule generate exactly the same thing as four steps of the "Flip if <condition>" rule!

So we only need to analyze the "Flip if <condition>" rules....

Follow the links in the table to see the analyses.

12-22-98