Problem 13

What limit sets can cellular automata produce?

Not all possible sets of configurations can be produced as limit sets of cellular automata. For the number of distinct cellular automaton rules, while infinite, is countable. Yet the number of possible sets of configurations is uncountable.

At each step in the evolution of an irreversible cellular automaton, a new set of configurations is excluded. The limit set consists of those configurations that are never excluded. The set of all excluded configurations is recursively enumerable, since each of its elements is found by a finite computation. Thus the limit sets for cellular automata are always the complements of recursively enumerable (co-r.e.) sets, and are therefore countable in number. Nevertheless, not every co-r.e. set is the limit set for a cellular automaton: one additional condition is that they must be translationally invariant. Thus for example, cellular automaton limit sets must contain either one configuration, or an infinite number of distinct configurations, and cannot consist of some other finite number of configurations [40]. Not every possible real number value of dimension or entropy can be realized by cellular automata; but the set that is realized presumably includes some values that are non-computable.

After any finite number of time steps, the set of configurations generated by a one-dimensional cellular automaton forms a regular formal language. For some cellular automata (essentially those in classes 1 and 2), the limit set is also a regular language. But in other cases, the limit set probably corresponds to a more complicated formal language. Explicit examples are known in which context-free and context-sensitive languages are obtained as limit sets [40]. In addition, cellular automata that are capable of universal computation can generate limit sets that are not recursive [40]. The generic behaviour is however not known: some more examples would be valuable.

When the limit set forms a regular language, the simplest description of it, in terms of a regular grammar or graph, can be found by a finite algorithm. The size of this description can be used as a measure of the complexity of the set. However, for languages more complicated than regular ones, there is in general no finite algorithm to find the simplest grammar (e.g., [8]). The size of such a minimal grammar is thus formally non-computable. One may test a sequence of grammars, but the languages to which they lead cannot in general be enumerated by a computation of any bounded length.

Minimum grammar size is thus not a useful measure of complexity for complicated cellular automaton limit sets. Some other measure must be found. And in terms of this measure, one should be able to determine how the complexity of the behaviour of a cellular automaton, as revealed by the structure of its limit set, depends on the complexity of its local rule, or the values of and .

One may wonder what features of the local rule for a cellular automaton determine its global properties, and the structure of its limit set. Some simple observations may be made. For example, unless the local rule contains elements that give value 1 with neighbourhoods such as 001, no information can propagate in the cellular automaton, and class 1 or 2 behaviour must occur. But in general one expects that the problem is undecidable: the only way to determine many of the limiting properties of a cellular automaton is probably by explicit simulation of its evolution, for an infinite time.

As a practical matter, one may ask whether cellular automaton rules may be constructed to yield particular limit sets (cf. [41]), so that their evolution serves to filter out the components that appear in these limit sets. It is probably possible to construct cellular automata that yield any of some class of regular languages as limit sets. But one suspects that a construction for more complicated limit sets can be carried out only in very special cases.

previous  l  next