The tetrahedron network from page 476 is for example given in this representation by {1  {2, 3, 4}, 2  {1, 3, 4}, 3  {1, 2, 4}, 4  {1, 2, 3}} The list of nodes reached by following up to n connections from node i are then given by NodeLists[g_, i_, n_] := NestList[Union[Flatten[# /. g]] &, {i}, n] The network distance corresponding to the length of the shortest path between two nodes is given by Distance[g_, {i_, j_}] := Length[NestWhileList[ Union[Flatten[# /. g]] &, {i}, !

A fixed interval of time for the clock—as indicated by the length of the darker gray regions—corresponds to a progressively longer interval of time at rest. … If these were parallel, one would inevitably get not just pure time dilation, but a mixture of it and length contraction.

And indeed, as I will discuss at length in the next chapter , I believe that in general there is a close connection between universality and the appearance of complex behavior. … But with initial condition (e) of length 8 the pictures show Rules for symbolic systems known as combinators, first introduced in 1920, and proved universal by the mid-1930s.

With a list s of possible symbols, c[s, n] gives all possible expressions with LeafCount[expr]  n : c[s_, 1] = s; c[s_, n_] := Flatten[ Table[Outer[#1[#2] &, c[s, n - m], c[s, m]], {m, n - 1}]] There are a total of Binomial[2n - 2, n - 1] Length[s] n /n such expressions. When Length[s]  1 the expressions correspond to possible balanced sequences of opening and closing brackets (see page 989 ).

Implementation [of tag systems] With the rules for case (a) on page 94 given for example by {2, {{0, 0}  {1, 1}, {1, 0}  {}, {0, 1}  {1, 0}, {1, 1}  {0, 0, 0}}} the evolution of a tag system can be obtained from TSEvolveList[{n_, rule_}, init_, t_] := NestList[If[Length[#] < n, {}, Join[Drop[#, n], Take[#, n] /. rule]]&, init, t] An alternative implementation is based on applying to the list at each step rules such as {{0, 0, s___}  {s, 1, 1}, {1, 0, s___}  {s}, {0, 1, s___}  {s, 1, 0}, {1, 1, s___}  {s, 0, 0, 0}} There are a total of ((k r + 1 - 1)/(k - 1)) k n possible rules if blocks up to length r can be added at each step and k colors are allowed.

Implementation [of cyclic tag systems] With the rules for the cyclic tag system on page 95 given as {{1, 1}, {1, 0}} , the evolution can be obtained from CTEvolveList[rules_, init_, t_] := Map[Last, NestList[CTStep, {rules, init}, t]] CTStep[{{r_, s___}, {0, a___}}] := {{s, r}, {a}} CTStep[{{r_, s___}, {1, a___}}] := {{s, r}, Join[{a}, r]} CTStep[{u_, {}}] := {u, {}} The leading elements on many more than t successive steps can be obtained directly from CTList[rules_, init_, t_] := Flatten[Map[Last, NestList[CTListStep, {rules, init}, t]]] CTListStep[{rules_, list_}] := {RotateLeft[rules, Length[list]],Flatten[rules 〚 Mod[Flatten[Position[list, 1]], Length[rules], 1] 〛 ]}

Proof lengths in logic As discussed on page 1170 equivalence between expressions can always be proved by transforming to and from canonical form. … In practice it is usually extremely difficult to find the absolute shortest proof of a given logic theorem—and the exact length will depend on what axiom system is used, and what kinds of steps are allowed. … The picture below shows in each of the axiom systems from page 808 the lengths of the shortest proofs found by a version of Waldmeister (see page 1158 ) for all 582 equivalences (see page 818 ) that involve two variables and up to 3 Nand s on either side.

Network constraint systems Cases (a), (f) and (p) allow all networks that do not contain respectively cycles of length 1 (self-loops), cycles of length 3 or less, and cycles of length 5 or less.

If a particular part of an organism always grows, say, in a simple straight line, then it is fairly easy to imagine that natural selection could succeed in picking out the optimal length for any given environment. … Fourth, if random mutations can only, say, increase or decrease a length, then even if one mutation goes in the wrong direction, it is easy for another mutation to recover by going in the opposite direction.

So given a particular elementary cellular automaton one can then ask what other elementary cellular automata it can emulate using blocks up to a certain length. … But at least with blocks up to length 25, rule 30 for example is not able to emulate any non-trivial rules at all.