On the limit set of some universal cellular automata

Eric Goles; Alejandro Maass; Servet Martinez

doi:10.1016/0304-3975(93)90350-3

On the limit set of some universal cellular automata

Eric Goles
, Alejandro Maass
, Servet Martinez

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

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 language	English
Pages (from-to)	53-78
Number of pages	26
Journal	Theoretical Computer Science
Volume	110
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(93)90350-3
State	Published - 15 Mar 1993
Externally published	Yes

Access to Document

10.1016/0304-3975(93)90350-3

Cite this

@article{c5e7bdcafd234fe387c000c3199a4c66,

title = "On the limit set of some universal cellular automata",

abstract = "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.",

author = "Eric Goles and Alejandro Maass and Servet Martinez",

note = "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.",

year = "1993",

month = mar,

day = "15",

doi = "10.1016/0304-3975(93)90350-3",

language = "English",

volume = "110",

pages = "53--78",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

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 - https://www.scopus.com/pages/publications/0027559050

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 -

On the limit set of some universal cellular automata

Abstract

Access to Document

Fingerprint

Cite this