More gems are revealed
It seems almost as if we can reduce the neighbor counts from eleven bits down to ten. There are 1,296 states to represent which is a lot closer to ten bits than eleven.
If you look at the neighbor counts it is apparent that many combinations of values will never occur. For example, if the upper left cell has five neighbors the upper right must have at least two since they share neighbors. This is wasteful and it would be nice (and faster) to make the table even smaller. Only 472 states are actually ever used. We could shave off two more bits if we could find an efficient way to represent this!
How much information do we really need? There are twelve individual neighbors for the cell cluster. The straight-forward approach is to use twelve bits to represent their state but that is too large. We are taking advantange of the semantics of life since the rules are concerned only about the count and not the specific order so some information can be discarded and we’ll still get the same result. Can we do a better job of this?
Here’s one idea. Imagine a 4 x 4 grid where the cell cluster is in the center surrounded by neighbors. There are two cells on each side that are shared. The cells in the corner are specific to just one cell in the cluster. We can represent this as a four-digit base-3 number and a four-digit base-2 number. Uh oh, 3^4 * 2^4 is 1,296. We got exactly nowhere!
This is a neat little lesson in information theory. We get the benefit of avoiding overlap in the neighbors but at the expense of specifically representing the corner neighbor states. In this case the gain perfectly equals the loss.
The low-brow solution is to use a table. You could index it by the current state and the change-state. It would reduce the size of one table at the expense of adding another. It would also add a few instructions per cell cluster to access the second table. The net result looks like a performance loss.
On second thought, it is possible the table approach might not work at all. Perhaps we have thrown away so much information that it is impossible to update the state in an incremental fashion. Are 1,296 states the minimum required to permit incremental updating?
The question remains: Can it be done in fewer than eleven bits?
On to Part 6. Another insight, another solution
Back to the main page