Notes

Chapter 3: The World of Simple Programs

Section 6: Sequential Substitution Systems


Order of replacements [in sequential substitution systems]

For many sequential substitution systems the evolution effectively stops because a string is produced to which none of the replacements given apply. In most sequential substitution systems there is more than one possible replacement that can in principle apply at a particular step, so the order in which the replacements are tried matters. (Multiway systems discussed on page 497 are what result if all possible replacements are performed at each step.) There are however special sequential substitution systems (those with the so-called confluence property discussed on page 1036) in which in a certain sense the order of replacements does not matter.

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