On the limit set of some universal cellular automata

Eric Goles, Alejandro Maass, Servet Martinez

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


In this paper we construct a simulation of a Turing machine by cellular automata based on the equivalence between programmable machines and Turing machines. For this class of cellular automata we prove that the associated limit language is regular. We also introduce algebraic characteristics which reduce the study of the complexity of the limit language to the analysis of a class of one-symbol languages.

Original languageEnglish
Pages (from-to)53-78
Number of pages26
JournalTheoretical Computer Science
Issue number1
StatePublished - 15 Mar 1993
Externally publishedYes


Dive into the research topics of 'On the limit set of some universal cellular automata'. Together they form a unique fingerprint.

Cite this