Tutorials/Rules

OK, so you want to understand rules, or even make your own cellular automata? Here's the place to learn how!

Preliminaries

Some care needs to be taken to distinguish between rules, which are part of the specification of a cellular automaton (CA), the rules according to which patterns in that CA evolve; and rulestrings, which are string representations of rules in the previous sense.

There are several ways of specifying rules beyond rulestrings, such as rule integers or rule tables, and different rulestrings may yet represent the same rule. Nonetheless, in common parlance the term "rule" is often used where "rulestring" would be more appropriate.

Outer-totalistic rules

Outer-totalistic rules are defined in terms of birth and survival conditions: the circumstances under which dead cells get born, and live cells survive.

There's different ways of specifying these; two common ways to write rulestrings are called "B/S notation" and "S/B" notation respectively. Life itself is specified by "B3/S23" or "23/3", but since S/B notation has fallen out of style, we'll only be focussing on B/S notation for the rest of this tutorial.

So, let's look at Life's B3/S23. In Life:

• A dead cell gets born if and only if it has three live neighbors; this is expressed by "B3".
• A live cell survives if and only if it has two or three live neighbors; this is expressed by "S23".

Cell birth in Life: if the cells in purple are live, the center cell will be born in the next generation.
Cell survival in Life: if the cells in purple are live, the center cell will survive in the next generation.

As you can see, birth and survival conditions are each encoded as a string of numbers following the respective letter ("B" for birth, "S" for survival). Since there are eight cells directly neighboring a given cell, all numbers from 0 to 8 can be specified, and each combination yields a different outer-totalistic rule.

Let's look at two more examples. Day & Night has the rulestring B3678/S34678, so in this rule, dead cells get born if they have 3, 6, 7 or 8 live neighbors, and live cells survive if they have 3, 4, 6, 7 or 8 live neighbors. Live Free or Die has the rulestring B2/S0, so in this rule, dead cells are born if they have precisely two live neighbors, and live cells only survive if they have no live neighbors at all — if they are surrounded entirely by dead cells. (Knowing this, you can probably tell how the rule got its name.)

Why are these CAs called "outer-totalistic"? The reason is simply that a cell's fate depends on (in addition to the state of the cell itself) on the total number of live outer cells. Outer-totalistic CAs are also called semi-totalistic, in the sense that they are "sort of (but not quite)" totalistic in the sense of the next section.

There are many ways to generalize such CAs. For instance, one could:

• Take into account the (relative or absolute) alignment of live neighbors, in addition to their total count; this leads to non-totalistic rules.
• Change the definition of what constitutes a "neighbor", e.g. using the von Neumann neighbourhood rather than the Moore neighbourhood, or increasing the distance at which cells are considered (Larger than Life rules).
• Increase the number of states a cell can be in, up from 2 ("dead" and "live").
• Change the topology of the universe: operate on e.g. a cylinder, torus or Klein bottle, rather than an infinite plane.
• Increase the dimension of the universe, considering one-dimensional cellular automata (e.g. Wolfram's Rule 110), 3-dimensional cellular automata, etc.
• Change the tiling of the universe: instead of using a square tiling, use a hexagonal tiling or triangular tiling, or even exotic tilings such as hyperbolic or Penrose tilings.
• ...and much more.

Totalistic rules

Totalistic rules are a sub-class of outer-totalistic rules in which the center cell is not afforded special treatment anymore when determining its fate. With outer-totalistic rules, the center cell and the total number of live neighbors are considered separately; in totalistic rules, the center cell is counted like any other cell, and only the total number of live cells in the neighborhood, including the center cell, is used to determine evolution.

Totalistic rules can be described using B/S notation, of course; alternatively, they can be expressed by a string of digits listing the live-cells-in-the-neighborhood counts which lead to the center cell being alive in the next generation.

Let's look at an example. B3/S2 is an outer-totalistic rule (more precisely, a rulestring encoding a rule) in which dead cells get born if they have precisely three live neighbors, and live cells survive if they have precisely two live neighbors. But if a live cell has two live neighbors, that means the total number of live cells in the neighborhood is three as well — so this rule is actually not just outer-totalistic but also totalistic, and its totalistic rulestring would simply be 3.

Cell birth in B3/S2: if the cells in purple are live, the center cell will be born in the next generation.

Cell survival in B3/S2: if the cells in purple are live, the center cell will survive in the next generation.

Fredkin, also known as Replicator 2, is another example. Its rulestring is B1357/S02468; look closely, and you will see that this means that a cell will be alive in the next generation if and only if the number of live cells in its neighborhood is odd (1, 3, 5, 7 or 9). Its totalistic rulestring, therefore, is 13579.

Non-totalistic rules

Non-totalistic rules differ from outer-totalistic rules in that not only the number of live neighbors of a cell is considered when deciding whether the cell should be born (or survive, if it is already live) — birth and survival also depend on the relative alignment of the cell's live neighbors.

Rulestrings for non-totalistic rules are typically given in Hensel notation. As an example, let's look at a hypothetical rule, B2ek/S12. We understand "S12" well enough – a live cell survives if it has one or two live neighbors –, but what does "B2ek" mean?

Imagine, if you will, a cell with two live neighbors. How can these two live neighbors be aligned, relative to each other? All the following configurations are possible:

c	e	k	a	i	n

(Some of these configurations have mnemonic names; "c" stands for "corner", "e" for "edge", "k" for "knightwise", "a" for adjacent, and so on. Others are less obvious and simply have to be remembered, or looked up as necessary.)

For an outer-totalistic rule, say B2/S12, any of these configurations would cause the center cell to be born. By contrast, in non-totalistic rules, each configuration is considered separately: in B2ek/S12 a dead cell gets born if and only if it has two live neighbors which are in "e" or "k" alignment (as shown above).

For some neighbor counts, particularly 4, there is a fairly large number of possible alignments, so it is sometimes convenient to negate rather than specify, essentially saying "...in all but these alignments". As an example, consider the first non-totalistic rule ever explored, Just Friends, which is described by the rulestring B2-a/S12. In this rule, a dead cell will get born if it has two live neighbors... unless those two live neighbors are in "a" alignment! Cells in this rule don't like getting cozy; they're "just friends".

Non-isotropic rules

The above non-totalistic rules are sometimes called isotropic: although birth or survival of a cell may depend on the relative alignment of its live neighbors, no attempt is made to distinguish between the absolute alignment. Put another way, two live neighbors north and northwest of a cell will satisfy the "B2a" or "S2a" conditions, but so will two live neighbors south and southeast of the same cell.

Non-isotropic rules further distinguish such cases. This part of the tutorial isn't written yet; for now you may want to look at the rule integer article, which briefly talks about MAP strings, a different way of encoding rules as 512-bit strings unrelated to B/S notation that naturally lends itself to describing non-isotropic rules.

Rules with larger neighbourhoods

This part of the tutorial isn't written yet, either; for now you may want to look at the Larger than Life article, which talks about such rules.

Creating custom rules

Golly has powerful facilities to run a very large class of different rules. You want to create your own custom rules? Then look no further than the Creating custom rules tutorial. If you're not familiar with Golly yet, you may also want to take a look at the Golly tutorial first.