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 . … (When there are multiple rules in the multiway system, tighter constraints are obtained by combining them with And .)

Properties [of example multiway systems] For most of the rules shown, there ultimately turn out to be quite easy characterizations of what strings can be produced. • (a) At step t , the only new string produced is the one containing t black elements. • (b) All strings of length n containing exactly one black cell are produced—after at most 2n - 1 steps. • (c) All strings containing even-length runs of white cells are produced. • (d) The set of strings produced is complicated. … (See the first rule on page 778 .)

Rules achieving these bounds are: The result for 5 states is still unknown, but a machine taking 47,176,870 steps and leaving 4098 black cells was found by Heiner Marxen and Jürgen Buntrock in 1990. Its rule is: The pictures below show (a) the first 500 steps of evolution, (b) the first million steps in compressed form and (c) the number of black cells obtained at each step.

Indeed, given the rules for a discrete system, it is usually a rather straightforward matter to do a computer experiment to find out how the system will behave.

The rules shown are numbers 255 and 4.

Cellular automata with rules that specify that a cell should become black if any of its neighbors are already black.

And if this is so, then it means that at the lowest level, the rules for the universe need make no reference to particular particles.

And given only the underlying rule for a substitution system, it turns out to be fairly difficult to tell even roughly what the spectrum will be like.

So this implies that from a computational point of view even systems with quite different underlying structures will still usually show a certain kind of equivalence, in that rules can be found for them that achieve universality—and that therefore can always exhibit the same level of computational sophistication.

And indeed in the proof of the universality of rule 110 in the previous chapter extremely complicated initial conditions were used to perform even rather simple computations.