On the limit set of some universal cellular automata (Q1210540): Difference between revisions

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.