In these circuits, lumps of electric charge (in 2001 about half a million electrons each) flow through channels which cross to form various kinds of gates. … Devices like keyboards, mice and microphones convert input into data that is inserted into memory at certain fixed locations. … In an interpreted language, each piece of input effectively causes a fixed subprogram to be executed to perform an operation specified by that input.

Subtleties in defining how big the input to a computation really is can lead to at least apparently exponential lower bounds. … But this seems exponentially large if s is specified by its digit sequence in the original input regular expression. … If one sufficiently restricts the form of the underlying system then it sometimes becomes possible to establish meaningful lower bounds.

In cases (c) and (d), these fluctuations turn out to have a very regular nested form. … But in general one suspects that all these rules can be thought of as being like simple computer programs that take some representation of n as their input.

The maximum halting times for the first few sizes n are {5, 159, 161, 1021, 5419, 315391, 1978213883, 1978213885, 3018415453261} These occur for inputs {1, 2, 5, 10, 26, 34, 106, 213, 426} and correspond to outputs (each themselves maximal for given n ) 2^{3, 23, 24, 63, 148, 1148, 91148, 91149, 3560523} - 1 Such maxima often seem to occur when the input x has the form (20 4 s - 2)/3 (and so has digits {1, 1, 0, 1, 0, … , 1, 0} ). The output f[x] in such cases is always 2 u - 1 where u = Nest[(13 + (6# + 8)(5/2)^ IntegerExponent[6# + 8, 2])/6 &, 1, s + 1] One then finds that 6u + 8 has the form Nest[If[EvenQ[#], 5#/2, # + 21]&, 14, m] for some m , suggesting a connection with the number theory systems of page 122 .

., {1, 1}, 1, ___} (in the alternative form of page 888 ). For any input x one can test whether the machine will ever halt using u[{Reverse[IntegerDigits[x, 2]], 0}] u[list_] := v[Split[Flatten[list]]] v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a]  0, True, c  {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e  {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]] This test takes at most n/3 recursive steps, even though the original machine can take of order n 2 steps to halt.

But when meiosis forms egg and sperm cells they get only one version of each. … In the immune system blocks of DNA—and joins between them—are selected at random by microscopic chemical processes when antibodies are formed. Most animal behavior is ultimately controlled by electrical activity in nerve cells—and this can be affected by details of sensory input, as well as by microscopic chemical processes in individual cells and synapses (see page 1011 ).

Defining life Greek philosophers such as Aristotle defined life by the presence of some form of soul, and the idea that there must be a single unique feature associated with life has always remained popular. … It is sometimes thought significant that living systems perpetuate the use of only one chirality of molecules, but actually this can quite easily be achieved by various forms of non-chemical input without life.

Here are examples of how some of the basic Mathematica constructs used in the notes in this book work: • Iteration Nest[f, x, 3] ⟶ f[f[f[x]]] NestList[f, x, 3] ⟶ {x, f[x], f[f[x]], f[f[f[x]]]} Fold[f, x, {1, 2}] ⟶ f[f[x, 1], 2] FoldList[f, x, {1, 2}] ⟶ {x, f[x, 1], f[f[x, 1], 2]} • Functional operations Function[x, x + k][a] ⟶ a + k (# + k&)[a] ⟶ a + k (r[#1] + s[#2]&)[a, b] ⟶ r[a] + s[b] Map[f, {a, b, c}] ⟶ {f[a], f[b], f[c]} Apply[f, {a, b, c}] ⟶ f[a, b, c] Select[{1, 2, 3, 4, 5}, EvenQ] ⟶ {2, 4} MapIndexed[f, {a, b, c}] ⟶ {f[a, {1}], f[b, {2}], f[c, {3}]} • List manipulation {a, b, c, d} 〚 3 〛 ⟶ c {a, b, c, d} 〚 {2, 4, 3, 2} 〛 ⟶ {b, d, c, b} Take[{a, b, c, d, e}, 2] ⟶ {a, b} Drop[{a, b, c, d, e}, -2] ⟶ {a, b, c} Rest[{a, b, c, d}] ⟶ {b, c, d} ReplacePart[{a, b, c, d}, x, 3] ⟶ {a, b, x, d} Length[{a, b, c}] ⟶ 3 Range[5] ⟶ {1, 2, 3, 4, 5} Table[f[i], {i, 4}] ⟶ {f[1], f[2], f[3], f[4]} Table[f[i, j], {i, 2}, {j, 3}] ⟶ {{f[1, 1], f[1, 2], f[1, 3]}, {f[2, 1], f[2, 2], f[2, 3]}} Array[f, {2, 2}] ⟶ {{f[1, 1], f[1, 2]}, {f[2, 1], f[2, 2]}} Flatten[{{a, b}, {c}, {d, e}}] ⟶ {a, b, c, d, e} Flatten[{{a, {b, c}}, {{d}, e}}, 1] ⟶ {a, {b, c}, {d}, e} Partition[{a, b, c, d}, 2, 1] ⟶ {{a, b}, {b, c}, {c, d}} Split[{a, a, a, b, b, a, a}] ⟶ {{a, a, a}, {b, b}, {a, a}} ListConvolve[{a, b}, {1, 2, 3, 4, 5}] ⟶ {2a + b, 3a + 2b, 4a + 3b, 5a + 4b} Position[{a, b, c, a, a}, a] ⟶ {{1}, {4}, {5}} RotateLeft[{a, b, c, d, e}, 2] ⟶ {c, d, e, a, b} Join[{a, b, c}, {d, b}] ⟶ {a, b, c, d, b} Union[{a, a, c, b, b}] ⟶ {a, b, c} • Transformation rules {a, b, c, d} /. b  p ⟶ {a, p, c, d} {f[a], f[b], f[c]} /. f[a]  p ⟶ {p, f[b], f[c]} {f[a], f[b], f[c]} /. f[x_]  p[x] ⟶ {p[a], p[b], p[c]} {f[1], f[b], f[2]} /. f[x_Integer]  p[x] ⟶ {p[1], f[b], p[2]} {f[1, 2], f[3], f[4, 5]} /. f[x_, y_]  x + y ⟶ {3, f[3], 9} {f[1], g[2], f[2], g[3]} /. f[1] | g[_]  p ⟶ {p, p, f[2], p} • Numerical functions Quotient[207, 10] ⟶ 20 Mod[207, 10] ⟶ 7 Floor[1.45] ⟶ 1 Ceiling[1.45] ⟶ 2 IntegerDigits[13, 2] ⟶ {1, 1, 0, 1} IntegerDigits[13, 2, 6] ⟶ {0, 0, 1, 1, 0, 1} DigitCount[13, 2, 1] ⟶ 3 FromDigits[{1, 1, 0, 1}, 2] ⟶ 13 The Mathematica programs in these notes are formatted in Mathematica StandardForm . The following table specifies how to enter these programs in Mathematica InputForm , using only ordinary keyboard characters:

When the study of feedback and stability became popular in the 1940s, there were many results about how specific simple fixed or repetitive behaviors in time could emerge despite random input. … But in their usual form, they yield essentially only rather simple repetitive patterns.

With a rule given in this form, each step in the evolution of the mobile automaton corresponds to the function MAStep[rule_, {list_List, n_Integer}] /; (1 < n < Length[list]) := Apply[{ReplacePart[list, #1, n], n + #2}&, Replace[Take[list, {n - 1, n + 1}], rule]] The complete evolution for many steps can then be obtained with MAEvolveList[rule_, init_List, t_Integer] := NestList[MAStep[rule, #]&, init, t] (The program will run more efficiently if Dispatch is applied to the rule before giving it as input.)