Chapter 3: The World of Simple Programs

Section 10: Symbolic Systems

Order dependence [in symbolic systems]

The operation expr /. lhs->rhs in Mathematica has the effect of scanning the functional representation of expr from left to right, and applying rules whenever possible while avoiding overlaps. (Standard evaluation in Mathematica is equivalent to expr //. rules and uses the same ordering, while Map uses a different order.) One can have a rule be applied only once using

Module[{i=1}, expr /. lhs :> rhs /; i++==1]

Many symbolic systems (including the one on page 103) have the so-called Church-Rosser property (see page 1036) which implies that if a fixed point is reached in the evolution of the system, this fixed point will be the same regardless of the order in which rules are applied.

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