Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Multiway systems [and operator systems]

One can use ideas from operator systems to work out equivalences in multiway systems (compare page 1169). One can think of concatenation of strings as being an operator, in terms of which a string like "ABB" can be written f[f[a,b],b]. (The arguments to \[SmallCircle] should strictly be distinct constants, but no equivalences are lost by allowing them to be general variables.) Assuming that the rules for a multiway system come in pairs p->q, q->p, like "AB"->"AAA", "AAA"->"AB", these can be written as statements about operators, like a · b == (a · a) · a. The basic properties of concatenation then also imply that (a · b) · c == a · (b · c). And this means that the possible forms for the operator · correspond to possible semigroups. Given a particular such semigroup satisfying axioms derived from a multiway system, one can see whether the operator representations of particular strings are equal—and if they are not, then it follows that the strings can never be reached from each other through evolution of the multiway system. (Such operator representations are a rough analog for multiway systems of truth tables.) As an example, with the multiway system "AB"↔"BA" some possible forms of operators are shown below. (In this case these are the commutative semigroups. With k=2, elements 6 out of the total of 8 possible semigroups appear; with k=3, 63 out of 113, and with k=4, 1140 out of 3492—all as shown on page 805.) (See also page 952.)

Taking · to be each of these operators, one can work out a representation for any given string like "ABAA" by for example constructing the expression ((a · b) · a) · a and finding its value for each of the k^2 possible pairs of values of a and b. Then for each successive operator, the sets of strings where the arrays of values are the same are as shown below.

Ultimately the sets of strings equivalent under the multiway system are exactly those containing particular numbers of black and white elements. But as the pictures above suggest, only some of the distinctions between sets of strings are ever captured when any specific form for the operator is used.

Just as for operator systems, any bidirectional multiway system will allow a certain set of operators. (When there are multiple rules in the multiway system, tighter constraints are obtained by combining them with And.) And the pattern of results for simple multiway systems is roughly similar to those on page 805 for operator systems—although, for example, the associativity of concatenation makes it impossible for example to get the operators for Nand and basic logic.


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