3.15 Termination

Not all rules continue to evolve forever from a given initial state. Instead they can reach a fixed point where the rule no longer applies. If the rule depends only on a single relation, this can only happen at the very first step. But if the rule depends on multiple relations, it can happen after multiple steps. Among the 4702 rules with signature 2₂  3₂, 1788 rules eventually reach a fixed point starting from a self-loop initial condition, at least using our standard updating order. Their “halting time” decreases roughly exponentially, with the maximum being 7 steps, achieved by the rule:

The longest halting time for which connectedness is maintained is 3 steps, achieved for example by:

Among the 40,405 2₂  4₂ rules, 10,480 evolve to fixed points starting from self-loops. The maximum halting time is 13 steps; the maximum maintaining connectedness is 6 steps, achieved by:

Among the 353,462 2₂  5₂ rules, 67,817 (or about 19%) evolve to fixed points. The maximum halting time is 24 steps; the maximum maintaining connectedness is 10 steps, achieved for example by:

Among 2₃  3₃ rules

has halting time 20: