Impossible Strings for Cellular Automata
In the note on Cellular Automata we discussed a class of simple linear two-state automata in which each field value ft+1(j) is either 0 or 1, and is a fixed function of the three prior values ft(j-1), ft(j), and ft(j+1). We saw how the 256 distinct functions ("rules") of this type can be placed into 88 equivalence classes up to direction reversal and field value complementation. Furthermore, we noted that for any given rule there may be impossible (excluded) strings, i.e., strings that are not the successor of any string. For any given rule, we can list the total number of k-bit excluded strings for k = 1, 2, ... etc. This gives sequences of integers, and we found that there are only 31 distinct sequences. The members of each of the 88 equivalence classes of rules fall into one of these 31 "exclusion classes". The largest single exclusion class consists of the rules that do not exclude any strings. At the other extreme, Rule 0 excludes all but one string. In between these two extremes are the other 29 exclusion classes, with varying degrees of exclusivity.
Naturally any string that contains an excluded string is also excluded, so we are led to focus on the primitive excluded strings, i.e., strings that are excluded but that do not contain any proper substring that is excluded. Typically the number of primitive excluded strings is a partition function. For example, as discussed in Cellular Automata, the primitive excluded strings for exclusion class 62 (which includes Rule 110) are of the form "01*10" where the "*" consists of a certain number of "0" bits followed by some number (possibly zero) of "111" strings each followed by one or more "0" bits. Consequently, letting P62(k) denote the number of primitive excluded k-bit strings for Class 62, we find that this is equal to the number of ordered partitions of k-4-3n into exactly n+1 positive integers, for all n such that k-4-3n is greater than or equal to n+1. Thus the values of n range from 0 to the greatest integer less than or equal to (k-5)/4. The values of P62(k) for k = 1 to 17 are listed below.
0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, ...
These values satisfy the 4th-order linear recurrence relation
where we have omitted the subscript "62" on the right-hand P terms for convenience. The characteristic polynomial x4 - x3 - 1 is irreducible, and has the approximate roots
1.380277, -0.819172, 0.219447 0.914473i
Therefore, the sequence asymptotically increases by a factor of about 1.38 as k is incremented. Of course, since any string that contains one of these primitive excluded strings is excluded, the total number of excluded k-bit strings for Class 62 increases more rapidly. The values of this number, which we will denote as E62(k), are listed below for k = 1 to 17.
0, 0, 0, 0, 1, 5, 16, 43, 107, 255, 589, 1328, 2940, 6419, 13862, 29668, 63024, ...
These values, too, satisfy a linear recurrence, namely the 6th-order recurrence
(Again we have omitted the subscript "62" on the right-hand side.) The characteristic polynomial of this recurrence factors as
The total number of k-bit strings is obviously 2k, so the fraction of k-bit strings that are excluded is E(k)/2k, which approaches 1 as k increases. This isn't surprising, because all it takes is one small primitive excluded string to exclude "almost all" sufficiently long strings. In fact, several of the exclusion classes ( 0, 3, 4, 7, 14, and 29) have only a single primitive excluded string.
In general, for rule classes that have easily-characterized primitive excluded strings, it seems to be possible to find a linear recurrence for the P and E sequences. Here is a short list of characteristic polynomials and their factorizations for several E-classes:
Not surprisingly, each of the characteristic polynomials contains a factor of (x-2), and therefore 2 is the dominant root, causing each sequence (asymptotically) to roughly double on each step. In addition, we see that several other factors are shared by two or more of these polynomials. The factor (x-1) signifies a constant offset in the sequences for classes 0, 29, 46, and 62. We also see the "Fibonacci factor" (x2-x-1) in the polynomials for classes 4, 18, and 46, the 3rd-order Fibonacci factor (x3-x2-x-1) for classes 14 and 29, and the factor (x3-2x2+x-1) for classes 3 and 18.
We can also find recurrences for the numbers of primitive excluded strings for some of the rule classes. Here is a short list of the characteristic polynomials and their factorizations for a few of the rule classes with non-trivial P(k) sequences.
As in the case of Class 62, the primitive excluded strings for Classes 18 and 25 can be expressed in terms of partitions. For Class 18 the primitive excluded strings are "111" plus all the strings of the form 11*11 where "*" signifies an odd number of individual "1" bits separated by at least one "0" from every other "1". Thus the value of P18(k) is the number of ordered partitions of k-4-n into exactly n+1 positive parts for odd integers n such that k-4-n is greater than or equal to n+1. Hence n ranges over the odd integers from 1 to the greatest odd integer less than or equal to (k-5)/2. To illustrate, with k=16 the permissible values of n are 1, 3, and 5, so we need to count the numbers of ordered partitions of 11 into two parts, of 9 into four parts, and of 7 into six parts. This gives 10, 56, and 6 respectively, so the total is P18(16) = 72. Similarly the primitive excluded strings for Class 25 can be expressed in terms of restricted partitions, although the restriction is slightly more complicated.
The remaining six non-trivial P(k) sequences (i.e., those for the classes 37, 22, 94, 73, 41, and 26) do not appear to satisfy a linear recurrence of order 8 or less. It is not known whether they satisfy any higher-order linear recurrence, or if they have simple generating functions.