2.8 Termination

We have seen that there can be several ways to apply a particular rule to a configuration of one of our systems. It is also possible that there may be no way to apply a rule. This can happen trivially if the evolution of the system reduces the number of relations it contains, and at some point there are simply no relations left. It can also happen if the rule involves, say, only k-ary relations, but there are no k-ary relations in the configuration of the system.

In general, however, a rule can continue for any number of steps, but then get to a configuration where it can no longer apply. The rule below, for example, takes 9 steps to go from {{0,0,0},{0,0}} to a configuration that contains only a single 3-edge, and no 2-edges that match the pattern for the rule:

It can be arbitrarily difficult to predict if or when a particular rule will “halt”, and we will see later that this is to be expected on the basis of computational irreducibility [1:12.6].