Problem 12

Is regular language complexity generically non-decreasing with time in one-dimensional cellular automata?

The sets of configurations generated by cellular automaton evolution, starting say from all possible initial states, can be considered as formal languages. Each configuration corresponds to a word in the language, formed from a sequence of symbols representing site values, according to a definite set of grammatical rules. For one-dimensional cellular automata, it can be shown that the set of configurations generated after any finite number of time steps forms a regular formal language [7]. Thus the configurations correspond to the possible paths through a finite directed graph, whose arcs are labelled by the values that occur at each site. There is an algorithm to find the graph with the minimal number of nodes that represents a particular regular language [8, 38], in such a way that each word in the language corresponds to a unique path through the graph (deterministic finite automaton). This minimal graph provides a complete canonical description of the set generated by the cellular automaton evolution. From it properties such as topological entropy may be deduced. The entropy is in fact given by the logarithm of the largest eigenvalue of the adjacency matrix for the graph, which is an algebraic integer.

One characteristic of a regular language is the total size or number of nodes in its minimal graph. This quantity can be considered as a measure of the complexity of the regular language. The larger it is, the more complicated a subset of the space of possible symbol sequences the language corresponds to. gives in a sense the size of the shortest description of this subset, at least in terms of regular languages. The value of is in general bounded above by . The empirical studies done so far suggest that for class 1 and 2 cellular automata, in fact becomes constant after a few time steps, or increases at most as a polynomial with . For most class 3 and 4 cellular automata, however, appears to increase rapidly with time, though it usually stays far below the upper bound. There are a few cases where decreases slightly at a particular time step, but in general it seems that is usually non-decreasing with time. If this is indeed a general result, it gives a quantitative form to the qualitative statement that complexity seems to increase with time. It could be a principle for self-organizing systems analogous in generality but complementary in content to the law of entropy increase in thermodynamic systems.

If the non-decrease of is indeed a general result, then it should have a simple proof that depends on few of the properties of the system considered. A crucial property of cellular automata may be irreversibility, which leads to a progressive contraction in the set of configurations generated. As a consequence of this contraction, the set generated at each time step must correspond to a different regular language. But there are only a limited number of regular languages with complexities less than any particular value, and so the complexity of the language generated must increase, albeit slowly, with time. To find a complete bound, one must study the structure of the space of possible regular languages. It is clear that the number of regular languages of complexity is less than the number of labelled directed graphs with nodes, . The minimal graph for a regular language must have a trivial automorphism group; but the number of graphs with a given automorphism group does not appear to be known (e.g., [39]). Beyond the total number of regular languages, one may consider the network that represents the containment of regular languages, divided into zones of different . One suspects that this network is close to a tree, with a number of nodes increasing perhaps exponentially with depth .

previous  l  next