×

On the limit sets of cellular automata. (English) Zbl 0691.68060

Cellular automaton (CA) is a k-dimensional array of cells. In each of them a copy of one and the same finite automaton is situated. For this f.a., a rule is given that describes the state of it at time \(t+1\) as a function of the states of some neighbouring cells at time t. The configuration of CA is a corresponding array of states of these copies at any moment of time. The quiescent configuration (QC) is one in which all cells are in the quiescent state. The configuration is called limit for a CA iff it can be reached by this CA from the corresponding initial configurations at time \(t=1;2;3;... \). The limit set (LS) for CA is the set of all limit configurations of it. A number of emptiiness problems for LS of CA is studied. The main results are as follows. For \(k\geq 2\) it is undecidable whether the LS of a given k-dimensional CA consists of QC only; for \(k=1\) this is still open. For \(k\geq 1\) it is undecidable whether the LS of a k-dimensional CA contais a configuration with finite nonzero number of uniquiescent states. For one-dimensional CA a limit language is the set of all finite subwords of the limit configurations of it. There exists a CA whose limit language isn’t recursively enumerable.
Different modelling techniques are used. Some proofs are based on topological and categorial arguments. The exposition is extremely precise and clear.
Reviewer: A.Andzans

MSC:

68Q80 Cellular automata (computational aspects)
PDF BibTeX XML Cite
Full Text: DOI