Universal One-Dimensional Cellular Automata Derived for Turing Machines and its Dynamical Behaviour
This addresses the problem of universality in cellular automata theory for researchers in theoretical computer science, but it appears incremental as it builds on existing conversion methods.
The paper presents an algorithm that converts any Turing machine into a one-dimensional cellular automaton with 2-linear time, demonstrating its spatial dynamics through examples like binary sum, rule 110, and a universal reversible Turing machine.
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.