[Converting from CAs with] more colors Given a rule that involves three colors and nearest neighbors, the following converts each case of the rule to a collection of cases for a rule with two colors: CA3ToCA2[{a_, b_, c_}  d_] := Union[Flatten[Table[Thread[ Partition[Flatten[{l, a, b, c, r} /. coding], 11, 1] 〚 {2, 3, 4} 〛  (d /. coding)], {l, 0, 2}, {r, 0, 2}], 2]] coding = {0  {0, 0, 0}, 1  {0, 0, 1}, 2  {0, 1, 1}} The problem of encoding cells with several colors by blocks of black and white cells is related to standard problems in coding theory (see page 560 ). One approach is to use {1, 1} to indicate the boundary of each block, and then within each block to use all possible digit sequences which do not contain {1, 1} , as in the Fibonacci number system discussed on page 892 .

And part (d) finally shows the base 2 digits of the successive values attained by the second register when the first register has just decreased to zero. … But the actual behavior of the program is almost indistinguishable from what we have already seen with two registers.

One-element-dependence tag systems [emulating TMs] Writing the rule {3, {{0, _, _}  {0, 0}, {1, _, _}  {1, 1, 0, 1}}} from page 895 as {3, {0  {0, 0}, 1  {1, 1, 0, 1}}} the evolution of a tag system that depends only on its first element is obtained from TS1EvolveList[rule_, init_, t_] := NestList[TS1Step[rule, #] &, init, t] TS1Step[{n_, subs_}, {}] = {} TS1Step[{n_, subs_}, list_] := Drop[Join[list, First[list] /. subs], n] Given a Turing machine in the form used on page 888 the following will construct a tag system that emulates it: TMToTS1[rules_] := {2, Union[Flatten[rules /. … The configuration of the tape on each side of the head in the Turing machine evolution can be obtained from the tag system evolution using Cases[history, x : {a[_], ___}  Apply[{#1, Reverse[#2]} &, Map[ Drop[IntegerDigits[Count[x, #], 2], -1] &, {_b, _d}]]]

In connection with early work on chaos theory, it was noted that there are some systems that act like "full shifts", in the sense that the set of sequences they generate includes all possibilities—and corresponds to what one would get by starting with any possible number, then successively shifting digits to the left, and at each step picking off the leading digit. … 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 ).

The tree representation of rule (c) from page 83 was for example probably drawn by Leonardo Fibonacci in 1202. … Viewed in terms of digit sequences, example (d) from page 83 was discussed by Georg Cantor in 1883 in connection with his investigations of the idea of continuity. General relations between digit sequences and sequences produced by neighbor-independent substitution systems were found in the 1960s.

The pictures below show how many steps are needed to reach value 1 starting from different values of n . … In case (b), the number of steps is equal to the number of base 2 digits in n , while in case (c) it is determined by the number of 1's in the base 2 digit sequence of n .

ElementaryRule works by converting num into a base 2 digit sequence, padding with zeros on the left so as to make a list of length 8. The scheme for numbering rules works so that if the value of a particular cell is q , the value of its left neighbor is p , and the value of its right neighbor is r , then the element at position 8 - (r + 2(q + 2p)) in the list obtained from ElementaryRule will give the new value of the cell.

For whether one does calculations by hand, by mechanical calculator or by electronic computer, one always needs an explicit representation for numbers, typically in terms of a sequence of digits of a certain length. (From the 1930s to 1960s, some work was done on so-called analog computers which used electrical voltages to represent continuous variables, but such machines turned out not to be reliable enough for most practical purposes.) From the earliest days of electronic computing, however, great efforts were made to try to approximate a continuum of numbers as closely as possible.

Minimal cellular automata for sequences Given any particular sequence of black and white cells one can look for the simplest cellular automaton which generates that sequence as its center column when evolving from a single black cell (compare page 956 ). … (Note that for example in the s = 15 case the lowest-numbered rule exhibits a complex 350-step transient away from the center column.) … Of the 4 billion k = 2 , r = 2 cellular automata none turn out to be able to produce for example sequences corresponding to the cubes, powers of 3, Fibonacci numbers, primes, digits of √ 2 , or concatenation sequences.

In general, if one looks along a diagonal n cells in from either edge of the pattern, then the period of repetition can be at most 2 n . … The boundary that separates repetition on the left from randomness on the right moves an average of about 0.252 cells to the left at every step (compare page 949 ). … The first n elements can be found efficiently using Module[{a = 1}, Table[First[IntegerDigits[ a, a = BitXor[a, BitOr[2a, 4a]]; 2, i]], {i, n}]] The sequence does not repeat in at least its first million steps, and I would amazed if it ever repeats, but as of now I know of no rigorous proof of this. ( Erica Jen showed in 1986 that no pair of columns can ever repeat, and the arguments on page 1087 suggest that neither can the center column together with occasional neighboring cells.)