Universal one-dimensional cellular automata derived from turing machines

Sergio J. Martínez; Iván M. Mendoza; Genaro J. Martínez; Shigeru Ninagawa

Universal one-dimensional cellular automata derived from turing machines

Sergio J. Martínez, Iván M. Mendoza, Genaro J. Martínez, Shigeru Ninagawa

Escuela Superior de Cómputo (ESCOM)

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

3 Scopus citations

Abstract

Universality in cellular automata theory is a central problem studied and developed from their origins by John von Neumann. In this paper, we present an algorithm where any Turing machine can be converted to one-dimensional cellular automaton with a 2-linear time and display its spatial dynamics. Three particular Turing machines are converted in three universal one-dimensional cellular automata, they are: binary sum, rule 110 and a universal reversible Turing machine.

Original language	English
Pages (from-to)	121-138
Number of pages	18
Journal	International Journal of Unconventional Computing
Volume	14
Issue number	2
State	Published - 2019

Keywords

Cellular automata
Spatial dynamics
Turing machines
Universality

Cite this

@article{965d9357208c45f08a6d7410ed315224,

title = "Universal one-dimensional cellular automata derived from turing machines",

abstract = "Universality in cellular automata theory is a central problem studied and developed from their origins by John von Neumann. In this paper, we present an algorithm where any Turing machine can be converted to one-dimensional cellular automaton with a 2-linear time and display its spatial dynamics. Three particular Turing machines are converted in three universal one-dimensional cellular automata, they are: binary sum, rule 110 and a universal reversible Turing machine.",

keywords = "Cellular automata, Spatial dynamics, Turing machines, Universality",

author = "Mart{\'i}nez, {Sergio J.} and Mendoza, {Iv{\'a}n M.} and Mart{\'i}nez, {Genaro J.} and Shigeru Ninagawa",

note = "Publisher Copyright: {\textcopyright} 2019 Old City Publishing, Inc.",

year = "2019",

language = "Ingl{\'e}s",

volume = "14",

pages = "121--138",

journal = "International Journal of Unconventional Computing",

issn = "1548-7199",

publisher = "Old City Publishing",

number = "2",

}

TY - JOUR

T1 - Universal one-dimensional cellular automata derived from turing machines

AU - Martínez, Sergio J.

AU - Mendoza, Iván M.

AU - Martínez, Genaro J.

AU - Ninagawa, Shigeru

PY - 2019

Y1 - 2019

N2 - Universality in cellular automata theory is a central problem studied and developed from their origins by John von Neumann. In this paper, we present an algorithm where any Turing machine can be converted to one-dimensional cellular automaton with a 2-linear time and display its spatial dynamics. Three particular Turing machines are converted in three universal one-dimensional cellular automata, they are: binary sum, rule 110 and a universal reversible Turing machine.

AB - Universality in cellular automata theory is a central problem studied and developed from their origins by John von Neumann. In this paper, we present an algorithm where any Turing machine can be converted to one-dimensional cellular automaton with a 2-linear time and display its spatial dynamics. Three particular Turing machines are converted in three universal one-dimensional cellular automata, they are: binary sum, rule 110 and a universal reversible Turing machine.

KW - Cellular automata

KW - Spatial dynamics

KW - Turing machines

KW - Universality

UR - http://www.scopus.com/inward/record.url?scp=85067789844&partnerID=8YFLogxK

M3 - Artículo

AN - SCOPUS:85067789844

SN - 1548-7199

VL - 14

SP - 121

EP - 138

JO - International Journal of Unconventional Computing

JF - International Journal of Unconventional Computing

IS - 2

ER -

Universal one-dimensional cellular automata derived from turing machines

Abstract

Keywords

Other files and links

Fingerprint

Cite this