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*