(In case (e), for example, the equation is t n  -t n - 1 + t n - 2 .) … Standard examples of recursive sequences that do not come from linear recurrence relations include factorial f[1] = 1; f[n_] := n f[n - 1] and Ackermann functions (see below ). … A recurrence relation like f[0] = x; f[n_] := a f[n - 1] (1 - f[n - 1]) corresponds to an iterated map of the kind discussed on page 920 , and has complicated behavior for many rational x .

The number of such strings containing 2n characters is the n th Catalan number Binomial[2n, n]/(n + 1) (as obtained from the generating function (1 - Sqrt[1 - 4x])/(2x) ). The number of strings of depth d (and thus taking d steps to annihilate completely) is given by c[{n, n}, d] - c[{n, n}, d - 1] where c[{_, _}, -1] = 0; c[{0, 0}, _] = 1; c[{m_, n_}, _] := 0 /; n > m; c[{m_, n_}, d_] := Sum[c[{i, j}, d], {i, 0, m - 1}, {j, m - d, n - 1}] Several types of structures are equivalent to strings of balanced parentheses, as illustrated below.

The sequence {1, 2, 2, 1, 1, 2, …} defined by the property list  Map[Length, Split[list]] was suggested as a mathematical puzzle by William Kolakoski in 1965 and is equivalent to Join[{1, 2}, Map[First, CTEvolveList[{{1}, {2}}, {2}, t]]] It is known that this sequence does not repeat, contains no more than two identical consecutive blocks, and has at least very close to equal numbers of 1's and 2's.

More colors [in additive cellular automata] The pictures below show generalizations of rule 90 to k possible colors using the rule CAStep[k_Integer, a_List] := Mod[RotateLeft[a] + RotateRight[a], k] or equivalently Mod[ListCorrelate[{1, 0, 1}, a, 2], k] . … Mod[Binomial[t, n], k] is given for prime k by With[{d = Ceiling[Log[k, Max[t, n] + 1]]}, Mod[Apply[Times, Apply[Binomial, Transpose[ {IntegerDigits[t, k, d] , IntegerDigits[n, k, d] }], {1}]], k]] The patterns obtained for any k are nested. For prime k the total number of non-white cells down to step k m is (1/2k (k + 1)) m and the patterns have fractal dimension 1 + Log[k, (k + 1)/2] (see page 955 ).

The rules for the multiway system can then be given for example as {"AAB"  "BB", "BA"  "ABB"} The evolution of the system is given by the functions MWStep[rule_List, slist_List] := Union[Flatten[ Map[Function[s, Map[MWStep1[#, s] &, rule]], slist]]] MWStep1[p_String  q_String, s_String] := Map[StringReplacePart[s, q, #] &, StringPosition[s, p]] MWEvolveList[rule_, init_List, t_Integer] := NestList[MWStep[rule, #] &, init, t] An alternative approach uses lists instead of strings, and in effect works by tracing the internal steps that Mathematica goes through in trying out possible matchings. With the rule from above written as {{x___, 0, 0, 1, y___}  {x, 1, 1, y}, {x___, 1, 0, y___}  {x, 0, 1, 1, y}} MWStep can be rewritten as MWStep[rule_List, slist_List] := Union[Flatten[Map[ReplaceList[#, rule] &, slist], 1]] The case shown on page 206 is {"AB"  "", "ABA"  "ABBAB", "ABABBB"  "AAAAABA"} starting with {"ABABAB"} .

And in general if h is associative the result Nest[h[r, #]&, s, t] of t steps of evolution can be rewritten for example using the repeated squaring method as h[Fold[If[#2  0, h[#1, #1], h[r, h[#1, #1]]] &, r, Rest[IntegerDigits[t, 2]]], s] which requires only about Log[t] rather than t applications of h . As a very simple example, consider a system which starts with the integer 1, then at each step just adds 1. One can compute the result of 9 steps of evolution as 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 , but a better scheme is to use partial results and compute successively 1 + 1; 2 + 2; 1 + 4; 5 + 5 —which is what the repeated squaring method above does when h = Plus , r = s = 1 .

A particular case on which many studies have been done is the so-called iterated Prisoner's Dilemma, in which two players make a sequence of choices a and b to "cooperate" ( 1 ) or "defect" ( 2 ), each trying to maximize their score m 〚 a, b 〛 with m = {{1, -1}, {2, 0}} . … In the late 1980s similar studies were done on processes such as auctions (cf page 1015 ), and in the late 1990s on games such as Rock, Paper, Scissors (RoShamBo) (with m = {{0, -1, 1}, {1, 0, -1}, {-1, 1, 0}} ). (A simpler game—certainly played since antiquity—is Penny Matching or Evens and Odds, with m = {{1, -1}, {-1, 1}} .)

The fraction of possible register machines that do this starting from initial condition {1, {0, 0}} decreases steadily with program length n , reaching about 0.76 for n = 8 . The most common number of steps before halting is always n , while the maximum numbers of steps for n up to 8 is {1, 3, 5, 10, 16, 37, 215, 1280} where in the last case this is achieved by {i[1], d[2, 7], d[2, 1], i[2], i[2], d[1, 4], i[1], d[2, 3]}

Note the inequality 1 ≤ DigitCount[n, 2, 1] ≤ Log[2, n] . Formulas for DigitCount[n, 2, 1] include n - IntegerExponent[n!, 2] and 2n - Log[2, Denominator[Derivative[n][(1 - #) -1/2 &][0]/n!]]

But I have been fortunate over the years to employ a variety of talented assistants, who have helped the project in many different ways: Eric Berg (project management, 2000–2001), Jason Cawley (historical and philosophical issues, 2001–2002 and before), Matthew Cook (technical content, particularly constructions and proofs, 1991–1998), Andrew de Laix (technical content and book production systems, 1998–2002), Matthew Frank (mathematical and historical issues, 2001–2002), Andrea Gerlach (fact finding and checking, 1999–2002), David Hillman (constructions and other technical content, 1997–2001), Scott Koranda (book production systems and project management, 1996–1998), Ed Pegg, Jr.