On the limit set of some universal cellular automata (Q1210540)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the limit set of some universal cellular automata |
scientific article |
Statements
On the limit set of some universal cellular automata (English)
0 references
30 August 1993
0 references
Programmable machines (PM) cellular automata (CA) and Turing machines (TM) are studied. A morphism between PM and CAs is constructed; the equivalence between TM and PM is used to prove that there exist CAs simulating any TM whose limit languages are regular. It follows from this result that there is no direct relation between computational complexity of a CA and the limit language complexity. Some algebraic characteristics of PMs are used to reduce the study of the limit language complexity for CAs to the analysis of a class of one-symbols language.
0 references
programmable machines
0 references
cellular automata
0 references
Turing machines
0 references
morphism
0 references
computational complexity
0 references
limit language complexity
0 references
