Universal One-Dimensional Cellular Automata Derived for Turing Machines and its Dynamical Behaviour

Authors :: Martinez, Sergio J.
Mendoza, Ivan M.
Martinez, Genaro J.
Ninagawa, Shigeru
Source :: International Journal of Unconventional Computing 14(2) pages 121-138, 2019
Publication Year :: 2019
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.<br />Comment: 18 pages, 8 tables, 3 figures. https://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-14-number-2-2019/ijuc-14-2-p-121-138/

Subjects :: Nonlinear Sciences - Cellular Automata and Lattice Gases
Computer Science - Computation and Language
Computer Science - Data Structures and Algorithms
Computer Science - Logic in Computer Science

Database :: arXiv
Journal :: International Journal of Unconventional Computing 14(2) pages 121-138, 2019
Publication Type :: Report
Accession number :: edsarx.1907.04211
Document Type :: Working Paper

Tools