TY - JOUR
T1 - On the limit set of some universal cellular automata
AU - Goles, Eric
AU - Maass, Alejandro
AU - Martinez, Servet
N1 - Funding Information:
Correspondence to: E. Gales, Universidad de Chile, Facultad de Ciencias Fisicas y Matematicas, tamento de Ingenieria Matematica, Casilla 170-3 correo 3, Santiago, Chile. *This work has been done under grants FONDECYT 1211-91, 0040-90, 1208-91.
PY - 1993/3/15
Y1 - 1993/3/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0027559050&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(93)90350-3
DO - 10.1016/0304-3975(93)90350-3
M3 - Article
AN - SCOPUS:0027559050
SN - 0304-3975
VL - 110
SP - 53
EP - 78
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -