Manifold [properties and] undecidability Given a particular set of network substitution rules there is in general no finite way to decide whether any sequence of such rules exists that will transform particular networks into each other.

{i[r_]  Table[n + j p  (1 + n Prime[r] (-n + #) &), {j, 0, g - 1}], d[r_, k_]  Table[n + j p  If[Mod[j, Prime[r]]  0, -1 + k + (-n + #)/Prime[r] &, # + 1 &], {j, 0, g - 1}]}] &, prog]]]}] The rules for the arithmetic system are represented so that the system from page 122 becomes for example {2, {0  (3 #/2 &), 1  (3 (# + 1)/2 &)}} . … The evolution of the arithmetic system is given by ASEvolveList[{n_, rules_}, init_, t_] := NestList[(Mod[#, n] /. rules)[#] &, init, t] Given a value m obtained in the evolution of the arithmetic system, the state of the register machine to which it corresponds is {Mod[m, p] + 1, Map[Last, FactorInteger[ Product[Prime[i], {i, nr}] Quotient[m, p]]] - 1} Note that it is possible to have each successive step involve only multiplication, with no addition, at the cost of using considerably larger numbers overall.

For the rule {0  {0, 1}, 1  {1}} , m = {{1, 1}, {0, 1}} , and the number of elements at step t starting with {0} is just t . … For neighbor-independent rules, the growth for large t must follow an exponential or an integer power less than the number of possible colors. For neighbor-dependent rules, any form of growth can in principle be obtained.

Most games have rules which imply that if certain states are reached one player can be forced in the end to lose, regardless of what specific moves they make. And even though the underlying rules in the game may be simple, the pattern of such winning positions is often quite complex. … With more general rules it seems almost inevitable that much more complicated patterns will occur.

And what one finds is that in certain cases—notably in connection with nesting at critical points associated with phase transitions (see page 981 )—certain averages turn out to be the same as one would get if one did no blocking but just changed parameters ("coupling constants") in the underlying rules that specify the weighting of different configurations. … But only rarely do such transformations yield cellular automata whose rules are of the same type one started from. And in most cases such rules will not suffice even if one takes averages.

But how does one give rules for the evolution of such a system? … Such rules are known in mathematics as partial differential equations, and in fact they have been widely studied for about two hundred years.

And in my study of simple programs I have seen essentially the same phenomenon: that even when programs have quite different underlying rules, their overall behavior can be remarkably similar. So this suggests that a kind of universality exists in the types of behavior that can occur, independent of the details of underlying rules.

But the remarkable fact is that none of these methods seem to reveal any real regularities whatsoever in the rule 30 cellular automaton sequence. … Yet starting with a simple initial condition and then applying a simple cellular automaton rule constitutes a simple

And as an example of a simple approach to modelling this, one can consider having a collection of discrete eddies that occur at discrete positions in the fluid, and interact through simple cellular automaton rules. … A cellular automaton (rule 225) whose behavior is reminiscent of turbulent fluid flow.

In a system like a cellular automaton the underlying rules can be thought of as rough analogs of the machine instructions for a computer, while the initial conditions can be thought of as rough analogs of the program. Yet what we saw in the previous section is that in cellular automata not only can the underlying rules be simple, but the initial conditions can also be simple—consisting say of just a single black cell—and still the behavior that is produced can be highly complex.