(a_  s_)  (rtab 〚 i k + a + 1 〛  k 2r (s - 1) + 1 + Mod[i k + a, k 2r ]), {i, 0, k 2r - 1}]&, net], 1] where here elementary rule 126 is specified for example by {2, 1, Reverse[IntegerDigits[126, 2, 8]]} . … The result from MinNet for rule 126 is {{1  3}, {0  2, 1  1}, {0  2,1  3}} . In general MinNet will yield a network with the property that any allowed sequence of values corresponds to a path which starts from node 1.

CTToR110[rules_ /; Select[rules, Mod[Length[#], 6] ≠ 0 &]  {}, init_] := Module[{g1, g2, g3, nr = 0, x1, y1, sp}, g1 = Flatten[ Map[If[#1 === {}, {{{2}}}, {{{1, 3, 5 - First[#1]}}, Table[ {4, 5 - # 〚 n 〛 }, {n, 2, Length[#]}]}] &, rules] /. a_Integer  Map[({d[# 〚 1 〛 , # 〚 2 〛 ], s[# 〚 3 〛 ]}) &, Partition[c[a], 3]], 4]; g2 = g1 = MapThread[If[#1 === #2 === {d[22, 11], s3}, {d[ 20, 8], s3}, #1] &, {g1, RotateRight[g1, 6]}]; While[Mod[ Apply[Plus, Map[# 〚 1, 2 〛 &, g2, 30] ≠ 0, nr++; g2 = Join[ g2, g1]]; y1 = g2 〚 1, 1, 2 〛 - 11; If[y1 < 0, y1 += 30]; Cases[ Last[g2] 〚 2 〛 , s[d[x_, y1], _, _, a_]  (x1 = x + Length[a])]; g3 = Fold[sadd, {d[x1, y1], {}}, g2]; sp = Ceiling[5 Length[ g3 〚 2 〛 ]/(28 nr) + 2]; {Join[Fold[sadd, {d[17, 1], {}}, Flatten[Table[{{d[sp 28 + 6, 1], s[5]}, {d[398, 1], s[5]}, { d[342, 1], s[5]}, {d[370, 1], s[5]}}, {3}], 1]] 〚 2 〛 , bg[ 4, 11]], Flatten[Join[Table[bgi, {sp 2 + 1 + 24 Length[init]}], init /. {0  init0, 1  init1}, bg[1, 9], bg[6, 60 - g2 〚 1, 1, 1 〛 + g3 〚 1, 1 〛 + If[g2 〚 1, 1, 2 〛 < g3 〚 1, 2 〛 , 8, 0]]]], g3 〚 2 〛 }] s[1] = struct[{3, 0, 1, 10, 4, 8}, 2]; s[2] = struct[{3, 0, 1, 1, 619, 15}, 2]; s[3] = struct[{3, 0, 1, 10, 4956, 18}, 2]; s[4] = struct[{0, 0, 9, 10, 4, 8}]; s[5] = struct[{5, 0, 9, 14, 1, 1}]; {c[1], c[2]} = Map[Join[{22, 11, 3, 39, 3, 1}, #] &, {{63, 12, 2, 48, 5, 4, 29, 26, 4, 43, 26, 4, 23, 3, 4, 47, 4, 4}, {87, 6, 2, 32, 2, 4, 13, 23, 4, 27, 16, 4}}]; {c[3], c[4], c[5]} = Map[Join[#, {4, 17, 22, 4, 39, 27, 4, 47, 4, 4}] &, {{17, 22, 4, 23, 24, 4, 31, 29}, {17, 22, 4, 47, 18, 4, 15, 19}, {41, 16, 4, 47, 18, 4, 15, 19}}] {init0, init1} = Map[IntegerDigits[216 (# + 432 10 49 ), 2] &, {246005560154658471735510051750569922628065067661, 1043746165489466852897089830441756550889834709645}] bgi = IntegerDigits[9976, 2] bg[s_, n_] := Array[bgi 〚 1 + Mod[# - 1, 14] 〛 &, n, s] ev[s[d[x_, y_], pl_, pr_, b_]] := Module[{r, pl1, pr1}, r = Sign[BitAnd[2^ListConvolve[{1, 2, 4}, Join[bg[pl - 2, 2], b, bg[pr, 2]]], 110]]; pl1 = (Position[r - bg[pl + 3, Length[r]], 1 | -1] /. {}  {{Length[r]}}) 〚 1, 1 〛 ; pr1 = Max[pl1, (Position[r - bg[pr + 5 - Length[r], Length[r]], 1 | -1] /. {}  {{1}}) 〚 -1, 1 〛 ]; s[d[x + pl1 - 2, y + 1], pl1 + Mod[pl + 2, 14], 1 + Mod[pr + 4, 14] + pr1 - Length[r], Take[r, {pl1, pr1}]]] struct[{x_, y_, pl_, pr_, b_, bl_}, p_Integer : 1] := Module[ {gr = s[d[x, y], pl, pr, IntegerDigits[b, 2, bl]], p2 = p + 1}, Drop[NestWhile[Append[#, ev[Last[#]]] &, {gr}, If[Rest[Last[#]] === Rest[gr], p2--]; p2 > 0 &], -1]] sadd[{d[x_, y_], b_}, {d[dx_, dy_], st_}] := Module[{x1 = dx - x, y1 = dy - y, b2, x2, y2}, While[y1 > 0, {x1, y1} += If[Length[st]  30, {8, -30}, {-2, -3}]]; b2 = First[Cases[st, s[d[x3_, -y1], pl_, _, sb_]  Join[bg[pl - x1 - x3, x1 + x3], x2 = x3 + Length[sb]; y2 = -y1; sb]]]; {d[x2, y2], Join[b, b2]}] CTToR110[{{}}, {1}] yields blocks of lengths {7204, 1873, 7088} . … In the first two blocks, much of what one sees is just padding to prevent clock pulses on the left from hitting data in the middle too early on any given step.

. • 1700s and 1800s: The digits of π and other transcendental numbers are seen to exhibit apparent randomness (see page 136 ), but the idea of thinking about this randomness as coming from the process of calculation does not arise. • 1800s: The distribution of primes is studied extensively—but mostly its regularities, rather than its irregularities, are considered. … (See page 918 .) • Late 1950s: Ideas from dynamical systems theory begin to be applied to systems equivalent to 1D cellular automata, but details of specific behavior are not studied except in trivial cases. • Late 1950s: Idealized neural networks are simulated on digital computers, but the somewhat complicated behavior seen is considered mainly a distraction from the phenomena of interest, and is not investigated. … They discover various examples (such as "munching foos") that produce nested behavior (see page 871 ), but do not go further. • 1962: Marvin Minsky and others study many simple Turing machines, but do not go far enough to discover the complex behavior shown on page 81 . • 1963: Edward Lorenz simulates a differential equation that shows complex behavior (see page 971 ), but concentrates on its lack of periodicity and sensitive dependence on initial conditions. • Mid-1960s: Simulations of random Boolean networks are done (see page 936 ), but concentrate on simple average properties. • 1970: John Conway introduces the Game of Life 2D cellular automaton (see above ). • 1971: Michael Paterson considers a class of simple 2D Turing machines that he calls worms and that exhibit complicated behavior (see page 930 ). • 1973: I look at some 2D cellular automata, but force the rules to have properties that prevent complex behavior (see page 864 ). • Mid-1970s: Benoit Mandelbrot develops the idea of fractals (see page 934 ), and emphasizes the importance of computer graphics in studying complex forms. • Mid-1970s: Tommaso Toffoli simulates all 4096 2D cellular automata of the simplest type, but studies mainly just their stabilization from random initial conditions. • Late 1970s: Douglas Hofstadter studies a recursive sequence with complicated behavior (see page 907 ), but does not take it far enough to conclude much. • 1979: Benoit Mandelbrot discovers the Mandelbrot set (see page 934 ) but concentrates on its nested structure, not its overall complexity. • 1981: I begin to study 1D cellular automata, and generate a small picture analogous to the one of rule 30 on page 27 , but fail to study it. • 1984: I make a detailed study of rule 30, and begin to understand the significance of it and systems like it.

The Lincos language of Hans Freudenthal from 1960 was specifically designed for extraterrestrial communication. … In 1974 the bitmap image below was sent as a radio signal from the Arecibo radio telescope. At the left-hand end is a version of the pattern of digits from page 117 —but distorted so it has no obvious nested structure.

The argument for this as usually presented involves rather technical results from several fields. … And from the unprovability of consistency one can conclude that this must be impossible using the ordinary operation of induction in Peano arithmetic. … In general one can imagine characterizing the power of any axiom system by giving a transfinite number κ which specifies the first function  [ κ ] (see note above ) whose termination cannot be proved in that axiom system (or similarly how rapidly the first example of y must grow with x to prevent ∃ y p[x, y] from being provable).

The undecidability of PCP can be seen to follow from the undecidability of the halting problem through the fact that the question of whether a tag system of the kind on page 93 with initial sequence s ever reaches a halting state (where none of its rules apply) is equivalent to the question of whether there is a way to satisfy the PCP constraint TSToPCP[{n_, rule_}, s_] := Map[Flatten[IntegerDigits[#, 2, 2]] &, Module[{f}, f[u_] := Flatten[Map[{1, #} &, 3u]]; Join[Map[{f[Last[#]], RotateLeft[f[First[#]]]} &, rule], {{f[s], {1}}}, Flatten[ Table[{{1, 2}, Append[RotateLeft[f[IntegerDigits[j, 2, i]]], 2]}, {i, 0, n - 1}, {j, 0, 2 i - 1}], 1]]], {2}] Any PCP constraint can also immediately be related to the evolution of a multiway tag system of the kind discussed in the note below. … From looking at the structure of the individual pairs one can see that if there is a solution it must begin with pair 1 or pair 3, and end with pair 1. … Yet starting with pair 1, the upper string is longer by 2 A s, and the pairs are such that the length difference must always remain even—preventing the crossover from occurring.

Periods from 1 to 15 are represented by different rows, with period 1 at the bottom. … For periods up to 10, examples of such blocks in rule 90 are given by the digits of {0, 40, 24, 2176, 107904, 640, 96, 8421376, 7566031296234863392, 15561286137} For period 1 the possible blocks are and ; for period 2 and .

Note (c) for Chaos Theory and Randomness from Initial Conditions…And in the early 1940s Mary Cartwright and John Littlewood noted that van der Pol's equation could exhibit solutions somehow sensitive to all digits in its initial conditions. … But from many results in this book it is now clear that this is not correct. (Note that James Gleick 's 1987 popular book Chaos covers somewhat more than is usually considered chaos theory—including some of my results on cellular automata from the early 1980s.)

Operations on sequences of digits had been used since antiquity in doing arithmetic. … Two immediate threads emerged from von Neumann's work. … From at least the early 1940s, electronic or other digital delay lines or shift registers were a common way to store data such as digits of numbers, and by the late 1940s it had been noted that so-called linear feedback shift registers (see page 974 ) could generate complicated output sequences.

As discovered by Srinivasa Ramanujan in 1918 its fluctuations (see below) can be obtained from the formula 1/6 π 2 n Sum[Apply[Plus, Cos[2 π n Select[ Range[s], GCD[s, #]  1 &]/s]]/s 2 , {s, ∞ }] (c) Squares are taken to be of positive or negative integers, or zero. … Note that the total number of integers less than n which can be expressed as a sum of three squares increases roughly like 5n/6 , with fluctuations related to IntegerDigits[n, 4] .