Computation theory of cellular automata (Q1072705): Difference between revisions
From MaRDI portal
Latest revision as of 13:17, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computation theory of cellular automata |
scientific article |
Statements
Computation theory of cellular automata (English)
0 references
1984
0 references
Self-organizing behaviour in cellular automata is discussed as a computational process. Formal language theory is used to extend dynamical systems theory descriptions of cellular automata. The sets of configurations generated after a finite number of time steps of cellular automaton evolution are shown to form regular languages. Many examples are given. The sizes of the minimal grammars for these languages provide measures of the complexities of the sets. This complexity is usually found to be non-decreasing with time. the limit sets generated by some classes of cellular automata correspond to regular languages. For other automata they appear to correspond to more complicated languages. Many properties of these sets are then formally non-computable. It is suggested that such undecidability is common in these and other dynamical systems.
0 references
Self-organizing behaviour
0 references
regular languages
0 references
limit sets
0 references
0 references