On the limit set of some universal cellular automata
type: Item
instance of: scholarly article
title: On the limit set of some universal cellular automata
zbMATH Open document ID: 0774.68085
DOI: 10.1016/0304-3975(93)90350-3
author: Alejandro Maass
author: Servet Martínez
author: Eric Goles
published in: Theoretical Computer Science
publication date: 1993-08-30T00:00:00Z
review text: 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.
reviewed by: Ketty Peeva
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 179577
zbMATH Keywords: programmable machines
zbMATH Keywords: cellular automata
zbMATH Keywords: Turing machines
zbMATH Keywords: morphism
zbMATH Keywords: computational complexity
zbMATH Keywords: limit language complexity
MaRDI profile type: Publication
full work available at URL: 0304-3975(93)90350-3
OpenAlex ID: W2032010938
cites work: On certain formal properties of grammars
cites work: Finite state languages
cites work: On the Limit Sets of Cellular Automata
cites work: Q3805907
cites work: Q4079524
cites work: Q5592246
cites work: Q3862379
cites work: Q3802661
cites work: Q3915990
cites work: Q3820012
cites work: Q3988480
cites work: A six-state minimal time solution to the Firing squad synchronization problem
cites work: Q5590814
cites work: Subshifts of finite type and sofic systems
cites work: Computation theory of cellular automata
description: scientific article; zbMATH DE number 179577