The proof shown takes a total of 343 steps, and involves intermediate expressions with as many as 128 Nand s.

Iterated Maps and the Chaos Phenomenon The basic idea of an iterated map is to take a number between 0 and 1, and then in a sequence of steps to update this number according to a fixed rule or "map". Many of the maps I will consider can be expressed in terms of standard mathematical functions, but in general all that is needed is that the map take any possible number between 0 and 1 and yield some definite number that is also between 0 and 1.

The basic idea is to have some definite procedure that takes any word or other piece of data and derives from it a so-called hash code which is used to determine where the data will be stored. … So what this means is that regardless of what kind of data one is storing, it takes only a very simple program to set up a hashing scheme that lets one retrieve pieces of data very efficiently.

So are there computations that take still longer to do? … Example (h) is the most extreme among 3-state 2-color Turing machines: with the size 7 input 106 it already takes 1,978,213,883 steps

But at least at a formal level, logic can be viewed simply as a theory of functions that take on two possible values given variables with two possible values.

But as I discuss in Chapter 12 , when the behavior is complex it may take an irreducible amount of computational work to answer any given question about it.

But to develop the new kind of science that I describe in this book I have had no choice but to take several large steps at once, and in doing so I have mostly ended up having to start from scratch—with new ideas and new methods that ultimately depend very little on what has gone before. … But instead I have chosen to spend the effort to take things to the point where they are clear enough to be explained quite fully just in ordinary language and pictures.

This suggests that to determine whether a repetitive pattern with repeating blocks of size n exists may in general take a number of steps which grows more rapidly than any polynomial in n .

Sequential substitution systems [from cellular automata] Given a sequential substitution system with rules in the form used on page 893 , the rules for a cellular automaton which emulates it can be obtained from SSSToCA[rules_] := Flatten[{{v[_, _, _], u, _}  u, {_, v[rn_, x_, _], u}  r[rn + 1, x], {_, v[_, x_, _], _}  x, MapIndexed[ With[{r n = #2 〚 1 〛 , rs = #1 〚 1 〛 , rr = #1 〚 2 〛 }, {If[Length[rs]  1, {u, r[rn, First[rs]], _}  q[0, rr], {u, r[rn, First[rs]], _}  v[rn, First[rs], Take[rs, 1]]], {u, r[rn, x_], _}  v[rn, x, {}], {v[rn, _, Drop[rs, -1]], Last[rs], _}  q[Length[rs] - 1, rr], Table[{v[rn, _, Flatten[{___, Take[rs, i - 1]}]], rs 〚 i 〛 , _}  v[ rn, rs 〚 i 〛 , Take[rs, i]], {i, Length[rs] - 1, 1, -1}], {v[rn, _, _], y_, _}  v[rn, y, {}]}] & , rules /. s  List], {_, q[0, {x__, _}], _}  q[0, {x}], {_, q[0, {x_}], _}  r[1, x], {_, q[0, {}], x_}  r[1, x], {_, q[_, {___, x_}], _}  x, {_, q[_, {}], x_}  x, {_, x_, q[0, _]}  x, {_, _, q[n_, {}]}  q[n - 1, {}], {_, _, q[n_, {x___, _}]}  q[n - 1, {x}], {q[_, {}], _, _}  w, {q[0, {__, x_}], p[y_, _], _}  p[x, y], {q[0, {__, x_}], y_, _}  p[x, y], {p[_, x_], p[y_, _], _}  p[x, y], {p[_, x_], u, _}  x, {p[_, x_], y_, _}  p[x, y], {_, p[x_, _], _}  x, {w, u, _}  u, {w, x_, _}  w, {_, w, x_}  x, {_, r[rn_, x_], _}  x, {_, u, r[_, _]}  u, {_, x_, r[rn_, _]}  r[rn, x], {_, x_, _}  x}] The initial condition is obtained by applying the rule s[x_, y__]  {r[1, x], y} and then padding with u 's.

And indeed, if one takes the patterns from successive steps and stacks them on top of each other to form a three-dimensional object, as in the picture below, then this object has a very regular nested structure.