Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Comparison to multiway systems

Operator systems are normally based on equations, while multiway systems are based on one-way transformations. But for multiway systems where each rule p->q is accompanied by its reverse q->p, and such pairs are represented say by "AAB"↔"BBAA", an equivalent operator system can immediately be obtained either from

Apply[Equal, Map[Fold[#2[#1] &, x, Characters[#]] &, rules, {2}], {1}]

or from (compare page 1172)

Append[Apply[Equal, Map[Fold[f, First[#], Rest[#]] &[Characters[#]] &, rules, {2}], {1}], f[f[a, b], c] == f[a, f[b, c]]]

where now objects like "A" and "B" are treated as constants—essentially functions with zero arguments. With slightly more effort multiway systems with ordinary one-way rules can also be converted to operator systems. Converting from operator systems to multiway systems is more difficult, though ultimately always possible (see page 1156).

As discussed on page 898, one can set up operator evolution systems similar to symbolic systems (see page 103) that have essentially the same relationship to operator systems as sequential substitution systems do to multiway systems. (See also page 1172.)


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