But if the behavior of the system is computationally irreducible—as I suspect is so for the cellular automaton on the facing page and for many other systems with simple underlying rules—then the point is that ultimately no such shortcut is possible. … Yet what the picture on the facing page illustrates is that in fact undecidability can have quite obvious effects even with a very simple underlying rule and very simple initial conditions.

simple underlying rules—can generate at least as much complexity as we see in the components of typical living systems. … Indeed, following the discoveries in this book I have come to the conclusion that almost any general feature that one might think of as characterizing life will actually occur even in many systems with very simple rules.

But just using definite pathways—or definite underlying rules—does not in any way preclude intelligence. And in fact if one looks inside a human brain—say in the process of generating speech—one will no doubt also see definite pathways and definite rules in use.

But one of the main discoveries of this book is that in fact great complexity can arise even in systems with extremely simple underlying rules, so that in the end nothing with rules even as elaborate as human intelligence—let alone beyond it—is needed to explain the kind of complexity we see in nature.

Indeed, in my experience it is remarkable just how often even elementary cellular automata like rule 90 and rule 30 can be applied in one way or another to technological situations.

Capabilities [of sequential substitution systems] Even with the single rule {s[1, 0]  s[0, 1]} , a sequential substitution system can sort its initial conditions so that all 0's occur before all 1's.

The rules for updating such networks turn out to be somewhat more difficult to apply than those for the network systems discussed here.

[Turing] machine 596440 For any list of initial colors init , it turns out that successive rows in the first t steps of the compressed evolution pattern turn out to be given by NestList[Join[{0}, Mod[1 + Rest[FoldList[Plus, 0, #]], 2], {{0}, {1, 1, 0}} 〚 Mod[Apply[Plus, #], 2] + 1] 〛 &, init, t] Inside the right-hand part of this pattern the cell values can then be obtained from an upside-down version of the rule 60 additive cellular automaton, and starting from a sequence of 1 's the picture below shows that a typical rule 60 nested pattern can be produced, at least in a limited region.

Implementation [of TM cellular automaton] Given a non-deterministic Turing machine with rules in the form above, the rules for a cellular automaton which emulates it can be obtained from NDTMToCA[tm_] := Flatten[{{_, h, _}  h, {s, _c, _}  e, {s, _, _}  s, {_, s, c[i_]}  s[i], {_, s, x_}  x, {a[_, _], _s, _}  s, {_, a[x_, y_], s[i_]}  a[x, y, i], {x_, _s, _}  x, {_, _, s[i_]}  s[i], Map[Table[With[{b = (# 〚 Min[Length[#], z] 〛 &)[ {x, #} /. tm]}, If[Last[b]  -1, {{a[_], a[x, #, z], e}  h, {a[ _], a[x, #, z], s}  a[x, #, z], {a[_], a[x, #, z], _}  a[b 〚 2 〛 ], {a[x, #, z], a[w_], _}  a[b 〚 1 〛 , w], {_, a[w_], a[x, #, z]}  a[w]}, {{a[_], a[x, #, z], _}  a[b 〚 2 〛 ], {a[x, #, z], a[w_], _}  a[w], {_, a[w_], a[x, #, z]}  a[b 〚 1 〛 , w]}]], {x, Max[Map[# 〚 1, 1 〛 &, tm]]}, {z, Max[Map[Length[# 〚 2 〛 ] &, tm]]}] &, Union[Map[# 〚 1, 2 〛 &, tm]]], {_, x_, _}  x}]

The active node can move by following its above or below connections, in a way that is determined by a rule which depends on the local structure of the network. … The rule for this system is {{1, 1}  {{{{}, {1, 1}}, {2}}, 2}, {1, 2}  {{{2, 2}, {{}, {2, 2}}}, 2}, {2, 1}  {{{}, {2, 2}}, 2}, {2, 2}  {{{1, 2} ,{{1}, {2}}}, 1}, {2, 3}  {{{{1, 2}, {1}}, {{2}, {2, 1}}}, 2}, {2, 4}  {{{2, 2}, {{2, 1}, {}}}, 1}}