(At least for the 256 elementary cellular automata this iterated map is never chaotic.)

Another approach was to look at actual possible transformations between partitionings, and this led from the late 1950s to various studies of so-called shift-commuting block maps (or sliding-block codes)—which turn out to be exactly 1D cellular automata (see page 878 ).

. • 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.

With the state of a 2-color tag system encoded as an integer according to FromDigits[Reverse[list] + 1, 3] the following takes the rule for any such tag system (in the first form from page 894 ) and yields a primitive recursive function that emulates a single step in its evolution: TSToPR[{n_, rule_}] := Fold[Apply[c, Flatten[{#1, Array[p, # 2], c[r[z, c[r[p[1], s], c[r[z, p[2]], c[r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]], p[#2]]}]] & , c[c[r[p[1], s], p[1], c[r[p[1], r[z, c[s, c[s, s]]]], c[c[r[z, c[r[p[1], s], c[r[z, c[s, z]], c[r[p[1], r[z, c[r[p[1], s], c[r[z, p[2]], c[ r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]]], p[2], p[3]]], p[1]]], p[1], p[1]], p[1]], p[2]]], p[n + 1], MapIndexed[c[r[z, c[r[p[1], p[4]], p[2], p[3], p[4]]], c[r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[Length[#2] + 1]], # 1 〚 1 〛 , #1 〚 2 〛 ] & , Nest[Partition[#1, 2] & , Table[Nest[c[s, #] & z, FromDigits[Reverse[IntegerDigits[i, 2, n] /. rule] + 1, 3]], {i, 0, 2 n - 1}], n - 1], {0, n - 1}]], Range[n, 1, -1]] (For tag system (a) from page 94 this yields a primitive recursive function of size 325.)

Map[ ∂ # f &, p]), p]/Sqrt[Det[g]] In general the series in r may not converge, but it is known that at least in most cases only flat space can give a result that shows no correction to the basic r d form.

The number of steps before a machine with given rule halts can be computed from (see page 888 ) Module[{s = 1, a, i = 1, d}, a[_] = 0; MapIndexed[a[#2 〚 1 〛 ] = #1 &, Reverse[IntegerDigits[x, 2]]]; Do[{s, a[i], d} = {s, a[i]} /. rule; i -= d; If[i  0, Return[t]], {t, tmax}]] Of the 4096 Turing machines with s = 2 , k = 2 , 748 never halt, 3348 sometimes halt and 1683 always halt.

No doubt the analog of turbulence can occur, and certainly there is sensitive dependence on initial conditions (even non-Abelian plane waves involve iterated maps that show this).

One can then compute the Ricci tensor (R ik = R ijk j ) using RicciTensor = Map[Tr, Transpose[Riemann, {1, 3, 2, 4}], {2}] and this has 1/2 d(d + 1) independent components in d > 2 dimensions.

One marginally more complicated case effectively involving 13 neighbors is IsingEvolve[list_, t_Integer] := First[Nest[IsingStep, {list, Mask[list]}, t]] IsingStep[{a_, mask_}] := {MapThread[ If[#2  2 && #3  1, 1 - #1, #1]&, {a, ListConvolve[ {{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, a, 2], mask}, 2], 1 - mask} where Mask[list_] := Array[Mod[#1 + #2, 2]&, Dimensions[list]] is set up so that alternating checkerboards of cells are updated on successive steps.