Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability

Multiway tag systems

As an extension of ordinary multiway systems one can generalize tag systems from page 93 to allow a list of strings at each step. Representing the strings by lists, one can write rules in the form

{{1, 1, s___} -> {s, 1, 0}, {1, s___} -> {s, 1, 0, 1}}

so that the evolution is given by

MWTSEvolve[rule_, list_, t_] := Nest[Flatten[Map[ReplaceList[#, rule] &, #], 1]&, list, t]

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