This was for example done by Julia Robinson in 1949 with Δ (or a + 1 ) and Mod[a, b]  0 . … Korec showed that finding elements in the nested pattern produced by the k = 3 cellular automaton with rule {{1, 1, 3}, {2, 2, 1}, {3, 3, 2}} 〚 #1, #2 〛 & (compare page 886 ) was also enough.

The evolution of the system for t steps can be obtained from SSEvolve[rule_, init_, t_, d_Integer] := Nest[FlattenArray[# /. rule, d] &, init, t] FlattenArray[list_, d_] := Fold[Function[{a, n}, Map[MapThread[Join, #, n] &, a, -{d + 2}]], list, Reverse[Range[d] - 1]] The analog in 3D of the 2D rule on page 187 is {1  Array[If[LessEqual[##], 0, 1] &, {2, 2, 2}], 0  Array[0 &, {2, 2, 2}]} Note that in d dimensions, each black cell must be replaced by at least d + 1 black cells at each step in order to obtain an object that is not restricted to a dimension d - 1 hyperplane.

The number of distinct machines that need to be considered increases as k increases for given s k (see note above ). s = 1 or k = 1 always yield trivial behavior. The fraction of machines that show non-repetitive behavior seems to increase roughly like (s - 1)(k - 1) (see page 888 ).

Cellular automaton combinators With k and s[k] representing respectively cell values 0 and 1 , a combinator f for which f[a -1 ][a 0 ][a 1 ] gives the new value of a single cell in an elementary cellular automaton with rule number m can be constructed as Apply[p[p[p[#1][#2]][p[#3][#4]]][p[p[#5][#6]][p[#7][ #8]]] /. {0  k, 1  s[k]} &, IntegerDigits[m, 2, 8]] //. crules where p = ToC[z[y][x], {x, y, z}] //. crules The resulting combinator has size 61, but for specific rules somewhat smaller combinators can be found—an example for rule 90 is s[k[k]][s[s][k[s[s[s[k][k]][k[s[k]]]][k[k]]]]] with size 16. To emulate cellular automaton evolution one starts by encoding a list of cell values by the single combinator p[num[Length[list]]][ Fold[p[Nest[s, k, #2]][#1] &, p[k][k], list]] //. crules where num[n_] := Nest[inc, s[k], n] inc = s[s[k[s]][k]] One can recover the original list by using Extract[expr, Map[Reverse[IntegerDigits[#, 2]] &, 3 + 59(16^Range[Depth[expr[s[k]][s][k] //. crules] - 1, 1, -1] - 1)/ 15)]]/. {k  0, s[k]  1} In terms of the combinator f a single complete step of cellular automaton evolution can be represented by w = cr[p[inc[inc[x[s[k]]]]][ inc[x[s[k]]][cr[p[y[s[k]][k]][p[y[s[k]][s[k]]][y[k]]], {y}]][p[x[s[k]][cr[p[p[f[y[k][k][k][s[k]]][ y[k][k][s[k]]][y[k][s[k]]]][y[s[k]]]][y[k][k]], {y}]][ p[p[k][k]][p[k][x[k]]]][s[k]]][p[k][p[k][k]]]][k]], {x}] cr[expr_, vars_] := ToC[expr //. crules, vars] where there is padding with 0 on either side.

And in general, the probabilities for all 8 possible combinations of 3 cells are given by probs = Apply[Times, Table[IntegerDigits[8 - i, 2, 3], {i, 8}] /. {1  p, 0  1 - p}, {1}] In terms of these probabilities the density at the next step in the evolution of cellular automaton with rule number m is then given by Simplify[probs . … The stable density after many steps is then given by Solve[3 p (1 - p) 2  p, p] , so that p  1 - 1/ √ 3 or approximately 0.42. … (For rules 90 and 30 the functions obtained after one step are respectively 2 p (1 - p) and p (2 p 2 - 5 p + 3) , both of which turn out to imply correct final densities of 1/2 ).

Random walks In one dimension, a random walk with t steps of length 1 starting at position 0 can be generated from NestList[(# + (-1)^Random[Integer])&, 0, t] or equivalently FoldList[Plus, 0, Table[(-1)^Random[Integer], {t}]] A generalization to d dimensions is then FoldList[Plus, Table[0, {d}], Table[RotateLeft[PadLeft[ {(-1)^Random[Integer]}, d], Random[Integer, d - 1]], {t}]] A fundamental property of random walks is that after t steps the root mean square displacement from the starting position is proportional to √ t . … As mentioned on page 1082 , the frequency spectrum Abs[Fourier[list]] 2 for a 1D random walk goes like 1/ ω 2 . … For example, in 1D and 2D, there is probability 1 that a particle will eventually return to its starting point.

(the surface area is d s[d] r d - 1 ). … Such a circle has area 2 π a 2 (1 - Cos[r/a]) = π r 2 (1 - r 2 /(12 a 2 ) + r 4 /(360a 4 ) - …) In the d -dimensional space corresponding to the surface of a (d + 1) -dimensional sphere of radius a , the volume of a d -dimensional sphere of radius r is similarly given by d s[d] a d Integrate[Sin[ θ ] d - 1 , { θ ,0, r/a}] = s[d] r d (1 - d (d - 1) r 2 /((6 (d + 2))a 2 + (d (5d 2 - 12d + 7))r 4 /((360 (d + 4))a 4 ) …) where Integrate[Sin[x] d - 1 , x] = -Cos[x] Hypergeometric2F1[1/2, (2 - d)/2, 3/2, Cos[x] 2 ] In an arbitrary d -dimensional space the volume of a sphere can depend on position, but in general it is given by s[d] r d (1 - RicciScalar r 2 /(6(d + 2)) + …) where the Ricci scalar curvature is evaluated at the position of the sphere. (The space corresponding to a (d + 1) -dimensional sphere has RicciScalar = d(d - 1)/a 2 .)

Note that the forms involve numerical values -1 and +1, corresponding to cells colored white and black.

And once again the numbers appear as coefficients, but now in the expansion of powers of 1 + x + x 2 rather than of 1 + x .

({a_, b_, c_}  d_)  ({1, 2a, 2b, 2c}  {2d, 1, 2b, 2c}), {{1, 0, 0}  {0, 0}, {0}  {1, 0, 0, 0}}] The initial condition {0, 0, 2, 0, 0} for the sequential substitution system corresponds to a single black cell surrounded by white cells in the cellular automaton.