For equations of the form ∂ tt u[t, x]  ∂ xx u[t, x] + f[u[t, x]] one can set up a simple finite difference method by taking f in the form of pure function and creating from it a kernel with space step dx and time step dt : PDEKernel[f_, {dx_, dt_}] := Compile[{a,b,c,d}, Evaluate[(2 b - d) + ((a + c - 2 b)/dx 2 + f[b]) dt 2 ]] Iteration for n steps is then performed by PDEEvolveList[ker_, {u0_, u1_}, n_] := Map[First, NestList[PDEStep[ker, #]&, {u0, u1}, n]] PDEStep[ker_, {u1_, u2_}] := {u2, Apply[ker, Transpose[ {RotateLeft[u2], u2, RotateRight[u2], u1}], {1}]} With this approach an approximation to the top example on page 165 can be obtained from PDEEvolveList[PDEKernel[ (1 - # 2 )(1 + #)&, {.1, .05}], Transpose[ Table[{1, 1} N[Exp[-x 2 ]], {x, -20, 20, .1}]], 400] For both this example and the middle one the results converge rapidly as dx decreases.

Ulam systems Having formulated the system around 1960, Stanislaw Ulam and collaborators (see page 877 ) in 1967 simulated 120 steps of the process shown below, with black cells after t steps occurring at positions Map[First, First[Nest[UStep[p[q[r[#1], #2]] &, {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, #] &, ({#, #} &)[{{{0, 0}, {0, 0}}}], t]]] UStep[f_, os_, {a_, b_}] := {Join[a, #], #} &[f[Flatten[ Outer[{#1 + #2, #1} &, Map[First, b], os, 1], 1], a]] r[c_]:= Map[First, Select[Split[Sort[c], First[#1]  First[#2] &], Length[#]  1 &]] q[c_, a_] := Select[c, Apply[And, Map[Function[u, qq[#1, u, a]], a]] &] p[c_]:= Select[c, Apply[And, Map[Function[u, pp[#1, u]], c]] &] pp[{x_, u_}, {y_, v_}] := Max[Abs[x - y]] > 1 || u  v qq[{x_, u_}, {y_, v_}, a_] := x  y || Max[Abs[x - y]] > 1 || u  y || First[Cases[a, {u, z_}  z]]  y These rules are fairly complicated, and involve more history than ordinary cellular automata.

When s max  ∞ , f[s] = a s Sin[s] yields 2D shapes that are basically nested, with pieces overlapping for Abs[a] < 1 .

. • 1906: Axel Thue studies simple substitution systems (see page 893 ) and finds behavior that seems complicated—though it turns out to be nested. • 1910s: Gaston Julia and others study iterated maps, but concentrate on properties amenable to simple description. • 1920: Moses Schönfinkel introduces combinators (see page 1121 ) but considers mostly cases specifically constructed to correspond to ordinary logical functions. • 1921: Emil Post looks at a simple tag system (see page 894 ) whose behavior is difficult to predict, but failing to prove anything about it, goes on to other problems. • 1920: The Ising model is introduced, but only statistics of configurations, and not any dynamics, are studied. • 1931: Kurt Gödel establishes Gödel's Theorem (see page 782 ), but the constructions he uses are so complicated that he and others assume that simple systems can never exhibit similar phenomena. • Mid-1930s: Alan Turing , Alonzo Church , Emil Post, etc. introduce various models of computation, but use them in constructing proofs, and do not investigate the actual behavior of simple examples. • 1930s: The 3n + 1 problem (see page 904 ) is posed, and unpredictable behavior is found, but the main focus is on proving a simple result about it. • Late 1940s and 1950s: Pseudorandom number generators are developed (see page 974 ), but are viewed as tricks whose behavior has no particular scientific significance. • Late 1940s and early 1950s: Complex behavior is occasionally observed in fairly simple electronic devices built to illustrate ideas of cybernetics, but is usually viewed as something to avoid. • 1952: Alan Turing applies computers to studying biological systems, but uses traditional mathematical models rather than, say, Turing machines. • 1952-1953: John von Neumann makes theoretical studies of complicated cellular automata, but does not try looking at simpler cases, or simulating the systems on a computer. • Mid-1950s: Enrico Fermi and collaborators simulate simple systems of nonlinear springs on a computer, but do not notice that simple initial conditions can lead to complicated behavior. • Mid-1950s to mid-1960s: Specific 2D cellular automata are used for image processing; a few rules showing slightly complex behavior are noticed, but are considered of purely recreational interest. • Late 1950s: Computer simulations of iterated maps are done, but concentrate mostly on repetitive behavior. … 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.

(Notably, FoldList normally seems more difficult to understand than NestList .)

Other examples [of substitution systems] (a) (Period-doubling sequence) After t steps, there are a total of 2 t elements, and the sequence is given by Nest[MapAt[1 - # &, Join[#, #], -1]&, {0}, t] .

Quadratic residue sequences As an outgrowth of ideas related to RSA cryptography it was shown in 1982 by Lenore Blum , Manuel Blum and Michael Shub that the sequence Mod[NestList[Mod[# 2 , m] &, x0, n], 2] discussed on page 975 has the property that if m=p q with p and q primes (congruent to 3 modulo 4) then any systematic regularities detected in the sequence can eventually be used to discover factors of m .

The first one on the bottom (with 63 comparisons) has a nested structure and uses the method invented by Kenneth Batcher in 1964: Flatten[Reverse[Flatten[With[{m = Ceiling[Log[2, n]] - 1}, Table[With[{d = If[i  m, 2 t , 2 i + 1 - 2 t ]}, Map[ {0, d} + # &, Select[Range[n - d], BitAnd[# - 1, 2 t ]  If[i  m, 0, 2 t ] &]]], {t, 0, m}, {i, t, m}]], 1]], 1] The second one on the bottom also uses 63 comparisons, while the last one is the smallest known for n = 16 : it uses 60 comparisons and was invented by Milton Green in 1969.

This notion was already suggested in pictures by Leonardo da Vinci from around 1510, and in Japanese pictures (notably by Katsushika Hokusai ) from around 1800 showing ocean waves breaking into precisely nested tongues of water.

With a list of length n , Nest[NLFSRStep[f, taps, #] &, list, n] gives one step in the evolution of the cellular automaton in a register of width n , with a certain kind of spiral boundary condition.