Transition (rule definition)

The elementary unit of a cellular-automaton rule definition is commonly called a transition. Every non-trivial CA rule is made up of one or more transitions. Each transition is a combination of a condition plus an action that should be taken if that condition is met.

In outer-totalistic rules

In the "Life-like" outer-totalistic rule space, there are 18 possible transitions, usually denoted 'B0' through 'B8' and 'S0' through 'S8'. 'B2', for example, specifies the condition that a cell has exactly two living neighbors, plus the "B" action, birth. If a cell is following a rule that includes the B2 transition, then the cell's state will change from 0 to 1 when the two-neighbors condition is met.

The nine "S" transitions specify the same range of neighbor-count conditions, plus the "S" action, survival.

Example

The standard rulestring for Conway's Life is "B3/S23". This is a slightly abbreviated encoding of the three outer-totalistic transitions that make up the Life rule -- "B3" (birth when there are three neighbors), "S2" (survival when there are two neighbors), and "S3" (survival when there are three neighbors).

Complementary transitions

A rule such as "B3/S23" is assumed to provide instructions for all possible situations that can arise -- including all transitions complementary to the stated transitions. If we list the subset of conditions where a cell is born, it's assumed that we don't also have to explicitly list the conditions where a cell is not born; the same goes for survival and non-survival.

• if there's no matching condition that says a cell will be born, the cell will not be born:  it will start in state 0 and end in state 0, a transition sometimes known as "stagnation" or "abstain" (abbreviation 'A', though this is seldom used).
• If there's no matching condition that says a cell will survive, the cell will die (abbreviation "D", also not much used.)

Thus Conway's Life rules could theoretically be written as "A01245678/D0145678", but not surprisingly the simpler "B3/S23" is almost universally used instead!

In isotropic rules

Rulespaces other than the "Life-like" rules have different sets of elementary transitions.  For isotropic rules, for example, there are 102 elementary transitions that subdivide the 18 outer-totalistic ones.  The size of a CA rulespace depends on the number of elementary transitions making up that rulespace; thus there are 2¹⁸ outer-totalistic Life-like rules, but 2¹⁰² distinct isotropic rules.

Example

• "S2" can be subdivided into S2c, S2e, S2k, S2a, S2i, and S2n isotropic transitions
• "B3" can be subdivided into B3c, B3e, B3k, B3a, B3i, B3n, B3y, B3q, B3j, and B3r
• "S3" can be subdivided into S3c, S3e, S3k, S3a, S3i, S3n, S3y, S3q, S3j, and S3r

So the standard Conway's Life rule could non-canonically be written as "B3aceijknqy/S2aceikn3aceijknqy", explicitly listing all of the isotropic transitions that make up the rule.

In lines of Golly rule tables

The transition table is the main part of a Golly ruletable, after the state, neighborhood, and symmetry definitions. The transition table is intended to be read line-by-line. In many cases, each line defines a single transition. If variables are used, a single line may represent a group of related transitions.

The term "transition table" is not specific to Golly; it has been used for many years to describe a set of transitions that make up a CA rule definition, including (for example) the data stored in various programmable metacells.

Order matters

The use of variables makes it possible for mutually contradictory transition definitions to be present in a valid rule table, due to the way the table is processed. The list of transitions is read in top-to-bottom order and the first matching transition is the one that is applied.

Many rule table definitions include "catch-all" transitions listed at the end of the transition table, for instance. The implication of such a "catch-all" transition is "here's the default action to take if none of the above conditions apply."

Example

Here is a simple two-transition Golly rule table definition that implements the outer-totalistic rule B12345678/S012345678, where cells turn on any time they have at least one neighbor:

var a = {0,1}

var b = a

var c = a

var d = a

var e = a

var f = a

var g = a

var h = a

var i = a

n_states:4

neighborhood:Moore

symmetries:rotate8

0, 0,0,0,0,0,0,0,0, 0

a, b,c,d,e,f,g,h,i, 1

The final two lines specify the transitions for this rule. The first of the two transition definitions (the one consisting of all zeroes) can be interpreted as "starting from state 0, with the condition that all eight neighbors are in state 0, remain in state 0".

The second transition definition, the one containing the variables 'a' through 'i', is a "catch-all" transition. It can be interpreted as "no matter what the starting state or neighbor states are, always change to state 1".

Consider the case where the starting cell and its neighbors are all zero. The two transition definitions both include conditions that match that case! But the all-zeroes transition definition is listed first in the table -- and the procedure for interpreting rule tables is to check each line in turn and apply the first matching condition.

In other words, when the rule represented by the above rule table is applied to a state-0 cell with all state-0 neighbors, the cell will remain in state 0. The second line of the transition table is simply ignored, because a matching condition has already been found in the first line.

If the two transition lines were reversed, that would define a different outer-totalistic rule (B012345678/S012345678). The "always change to state 1" transition would take precedence even in the all-zeroes case, and the all-zeroes transition would never be applied -- in fact it could be removed entirely without changing the behavior of the rule. If that rule table were simulated, every cell in the universe would instantly switch to state 1 and remain there -- potentially very different behavior from the rule with those two transitions in the opposite order.

See the RuleLoader article for more information and further references.

Similar terms

In common usage, an outer-totalistic or isotropic transition such as "B3" or "S4j" is often referred to as a "condition" instead of a "transition", commonly with an explicit prefix that re-confirms what happens to the state -- e.g., a "B3 birth condition" or an "S4j survival condition".

It is common practice to use either 'condition' or 'transition' to refer to an elementary unit of a rulestring like "B3" or "S4j" -- but depending on the context, 'condition' may be intended to refer only to the current states of a key cell and its neighbors, ignoring the future cell state specified by the "B" or "S" prefix.

See also

Transition (disambiguation)