With rule (a), however, it is fairly easy to see that a simple nested structure is produced, directly analogous to the one shown on page 509 . … The pictures on the facing page show what happens if at each step one allows not just a single replacement, but all replacements that do not overlap.

Using more complicated rules may be convenient if one wants, say, to reproduce the details of particular natural systems, but it does not add fundamentally new features. Indeed, looking at the pictures on the previous page one sees exactly the same basic themes as in elementary cellular automata.

But if one generalizes to neighbor-dependent substitution systems then it immediately becomes very straightforward to emulate cellular automata, as in the pictures below. … The systems shown are simple examples of neighbor-dependent substitution systems with highly uniform rules always yielding just one cell and corresponding quite directly to cellular automata.

Even when a cellular automaton mapping is surjective, it is still often many-to-one, in the sense that several input states can yield the same output state. (Thus for example additive rules such as 90 and 150, as well as one-sided additive rules such as 30 and 45 are always 4-to-1.) … And in such a case the cellular automaton mapping is one-to-one or bijective (an automorphism).

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]

One version posed as a problem by John Myhill in 1957 consists in setting up a rule in which all cells in a region go into a special state after exactly the same number of steps. … Note that this solution in effect constructs a nested pattern of any width (it does this by optionally including or excluding one additional cell at each nesting level, using a mechanism related to the decimation systems of page 909 ). If one drops the requirement of cells going into a special state, then even the 2-color elementary rule 60 shown on the left can be viewed as solving the problem—but only for widths that are powers of 2.

So long as one only ever looks at the original input and final output it turns out that one can construct a system that exhibits undecidability but is not universal. … As I discuss on page 1137 , almost all known proofs of undecidability in practice work by reduction to the halting problem for some universal system—this is, by showing that if one could resolve whatever is supposed to be undecidable then one could also solve the halting problem for a universal system. … To set up the generalized diagonal argument one needs a way to list all possible programs.

The picture below shows as one example what happens in a simple aggregation model.

One starts by assigning a continuous complex number value to each cell. … One might hope to be able to get an ordinary cellular automaton with a limited set of possible values by choosing a suitable θ . … One can generalize the setup to more dimensions or to allow n × n matrices that are elements of SU( n ).

A practical issue that arises is that if one repeatedly tries experiments with the same set of textures, then after a while one learns to discriminate these particular textures better.