A Class of Models with the Potential to Represent Fundamental Physics
  1. Introduction
  2. Basic Form of Models
  3. Typical Behaviors
  4. Limiting Behavior and Emergent Geometry
  5. The Updating Process for String Substitution Systems
  6. The Updating Process in Our Models
  7. Equivalence and Computation in Our Models
  8. Potential Relation to Physics
  9. Additional Material
  10. References
  11. Index

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:

{{x, y, z}, {u, x}} -> {{x, u, v}, {z, y}, {z, u}}
ResourceFunction["WolframModelPlot"][#, "MaxImageSize" -> 100] & /@ ResourceFunction[ "WolframModel"][{{x, y, z}, {u, x}} -> {{x, u, v}, {z, y}, {z, u}}, {{0, 0, 0}, {0, 0}}, 20, "StatesList"]

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].