Multiway System

A multiway system is a kind of substitution system in which multiple states are permitted at any stage. This accommodates rule systems in which there is more than one possible way to perform an update.


A simple example is a string substitution system. For instance, take the rules {AB->A,BA->B} and the initial condition ABA. There are two choices for how to proceed. Applying the first rule yields the evolution ABA toAA, while applying the second rule yields the evolution ABA->AB->A. So at the first step, there is a single state ({ABA}), at the second step there are two states {AA,AB}, and at the third step there is a single state {A}.

A path through a multiway system arising from a choice of which substitutions to make is called an evolution. Typically, a multiway system will have a large number of possible evolutions. For example, consider strings of As and Bs with the rule AB->BA. Then most strings will have more than one occurrence of the substring AB, and each occurrence leads down another path in the multiway system.

See also

Automated Prover, Branchial Graph, Branchial Space, Causal Invariance, Confluent, Multicomputational Paradigm, Reduction System, Sequential Substitution System, Substitution System, Term Rewriting System

This entry contributed by Todd Rowland

Explore with Wolfram|Alpha


Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 204-209 and 937-939, 2002.Wolfram, S. "Multicomputation with Numbers: The Case of Simple Multiway Systems." 9 Nov 2021.

Referenced on Wolfram|Alpha

Multiway System

Cite this as:

Rowland, Todd. "Multiway System." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications