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). The pictures below show the lowest-numbered cellular automaton rules that manage to generate repetitive sequences containing black cells with successively greater separations s.

Elementary (k = 2, r = 1) cellular automata can be found only up to separations s = 2. But k = 2, r = 2 cellular automata can be found for all separations up to 15, as well as 17, 19 and 23. (Note that for example in the s = 15 case the lowest-numbered rule exhibits a complex 350-step transient away from the center column.)

The pictures below show the lowest-numbered cellular automata that generate respectively powers of two, squares and the nested Thue–Morse sequence of page 83 (compare rule 150). 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.

If one looks not just at specific sequences, but instead at all 2ⁿ possible sequences of length n, one can ask how many cellular automaton rules (say with k = 2, r = 2) one has to go through in order to generate every one of these. The pictures below show on the left the last rules needed to generate any sequence of each successive length—and on the right the form of the sequence (as well as its continuation after length n). Since some different rules generate the same sequences (see page 956) one needs to go through somewhat more than 2ⁿ rules to get every sequence of length n. The sequences shown below can be thought of as being in a sense the ones of each length that are the most difficult to generate—or have the highest algorithmic information content. (Note that the sequence is the first one that cannot be generated by any of the 256 elementary cellular automata; the first sequence that cannot be generated by any k = 2, r = 2 cellular automata is probably of length 26.)