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. But from the discoveries in this book we now know that much simpler rules can also yield very complicated behavior. And as the pictures below show, this is true even just for parts of the rules above (s alone yields outer totalistic code 686 in 2D, and rule 90 in 1D).

Ulam also in 1967 considered the pure 2D cellular automaton with outer totalistic code 12 (though he stated its rule in a complicated way). As shown in the pictures below, when started from blocks of certain sizes this rule yields complex patterns—although nothing like this was noted in 1967.