Notes

Chapter 5: Two Dimensions and Beyond

Section 6: Multiway Systems


General properties [of multiway systems]

The merging of states (as done above by Union) is crucial to the behavior seen. Note that the pictures shown indicate only which states yield which states—not for example in how many ways the rules can be applied to a given state to yield a given new state.

If there was no merging, then if a typical state yielded more than one new state, then inevitably the total number of states would increase exponentially. But when there is merging, this need not occur—making it difficult to give probabilistic estimates of growth rates. Note that a given rule can yield very different growth rates with different initial conditions. Thus, for example, the growth rate for {"A" -> "AA", "AB" -> "BA", "BA" -> "AB"} is t^(n+1), where n is the number of initial B's. With most rules, states that appear at one step can disappear at later steps. But if "A" -> "A" and its analogs are part of the rule, then every state will always be kept, almost inevitably leading to overall nesting in pictures like those on page 208.

In cases where all strings that appear both in rules and initial conditions are sorted—so that for example A's appear before B's—any string generated will also be sorted, so it can be specified just by giving a list of how many A's and how many B's appear in it. The rule for the system can then be stated in terms of a difference vector—which for {"AB" -> "BBB", "ABB" -> "AAAB"} is {{-1,2},{2,-1}}. Given a list of string specifications, a step in the evolution of the multiway system corresponds to

Select[Union[Flatten[Outer[Plus, diff, list, 1], 1]], Abs[#] == # &]


From Stephen Wolfram: A New Kind of Science [citation]