pith. sign in

arxiv: 1907.04211 · v1 · pith:GGCSJODUnew · submitted 2019-07-06 · 🌊 nlin.CG · cs.CL· cs.DS· cs.LO

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

Sergio J. Martinez , Ivan M. Mendoza , Genaro J. Martinez , Shigeru Ninagawa This is my paper

Pith reviewed 2026-05-25 01:26 UTC · model grok-4.3

classification 🌊 nlin.CG cs.CLcs.DScs.LO
keywords cellular automataTuring machinesuniversalitysimulationone-dimensional automatadynamical behaviour
0
0 comments X

The pith

Any Turing machine converts to a one-dimensional cellular automaton that simulates it in linear time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives an algorithm that transforms an arbitrary Turing machine into a one-dimensional cellular automaton whose evolution reproduces the machine's computation. The simulation completes in time at most twice the number of steps taken by the original machine. Three concrete conversions are shown: a binary adder, the rule 110 automaton, and a universal reversible Turing machine. The resulting automata make the step-by-step tape contents visible as spatial patterns across the lattice.

Core claim

Any Turing machine can be systematically transformed into a one-dimensional cellular automaton that emulates it exactly with a simulation overhead of only a factor of two in time, enabling the display of the machine's computation as spatial patterns.

What carries the argument

The conversion algorithm that encodes Turing machine states, symbols, and head position into the cells and local rules of a one-dimensional cellular automaton.

If this is right

  • Known universal Turing machines yield universal one-dimensional cellular automata.
  • The spatial patterns of any Turing computation become directly observable in one dimension.
  • Rule 110 and other established systems acquire explicit Turing-machine origins through the mapping.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same mapping could be used to translate other models of computation into cellular automata with comparable efficiency.
  • Linear-time simulation removes a common objection that cellular automata are too slow to emulate sequential machines.
  • The technique may let researchers study the space-time diagrams of arbitrary Turing machines without building separate simulators.

Load-bearing premise

The generated cellular automaton reproduces the Turing machine's exact sequence of configurations without any loss of information or extra computational overhead beyond the stated linear-time bound.

What would settle it

Run the conversion on a simple Turing machine such as the binary adder and check whether, for inputs requiring more than a few dozen steps, the cellular automaton lattice ever diverges from the tape contents and head position produced by the original machine.

Figures

Figures reproduced from arXiv: 1907.04211 by Genaro J. Martinez, Ivan M. Mendoza, Sergio J. Martinez, Shigeru Ninagawa.

Figure 1
Figure 1. Figure 1: Behaviour of the Turing machine M and its equivalent cellular au￾tomaton CBS for the input string = 00101 + 00101 =. (left) Representation of the symbols. (center) Turing machine dynamics. (right) Cellular automaton dynamics. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Dynamical behaviour of the Turing machine [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Dynamical behaviour of the Turing machine [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript claims to present an algorithm converting any Turing machine to a one-dimensional cellular automaton that simulates the TM computation in 2-linear time, and applies the algorithm to three specific TMs (binary sum, Rule 110, and a universal reversible TM) while displaying the resulting spatial dynamics.

Significance. If the general construction were rigorously established with a proof of exact simulation, the result would supply a uniform embedding of arbitrary TM computations into 1D CAs, enabling systematic study of their dynamical properties and universality. The three explicit constructions provide concrete, potentially verifiable instances that illustrate the approach.

major comments (3)
  1. [Algorithm description and abstract] The abstract and the section describing the conversion algorithm assert a general procedure that works for arbitrary TMs with exact preservation of computation and a 2-linear time bound, yet supply no inductive argument, state-mapping lemma, or derivation establishing these properties beyond the three examples.
  2. [Introduction and algorithm section] The time-bound claim ('2-linear time') is stated without a definition of the time measure or a derivation showing how CA steps correspond to TM steps with a constant factor of 2 and no hidden overhead; this is load-bearing for the central simulation claim.
  3. [Examples and results section] The three concrete examples (binary sum, Rule 110, universal reversible TM) demonstrate spatial dynamics but do not establish the general claim, as they leave open the possibility of simulation divergence or extra overhead on other TMs not covered by the cases.
minor comments (2)
  1. [Abstract] The term '2-linear time' appears without an explicit definition or reference to a prior definition; a short clarification in the abstract or introduction would improve readability.
  2. [Figures] Figure captions for the spatial dynamics plots could include explicit labels for time steps, state encodings, and the correspondence to TM tape/head positions to aid interpretation.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The points raised correctly identify that the general simulation claim requires a more explicit formal justification than is currently provided by the algorithm description and examples alone. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: The abstract and the section describing the conversion algorithm assert a general procedure that works for arbitrary TMs with exact preservation of computation and a 2-linear time bound, yet supply no inductive argument, state-mapping lemma, or derivation establishing these properties beyond the three examples.

    Authors: The algorithm section presents a constructive mapping from TM states, symbols, and head position to CA cell states, with the design intended to ensure step-by-step preservation. We agree that this falls short of a rigorous proof and that an inductive argument or state-mapping lemma is needed to establish exact simulation for arbitrary TMs. In the revised manuscript we will add a lemma that defines the simulation invariant and proves by induction that every TM configuration is faithfully represented by a corresponding CA configuration at the appropriate time steps. revision: yes

  2. Referee: The time-bound claim ('2-linear time') is stated without a definition of the time measure or a derivation showing how CA steps correspond to TM steps with a constant factor of 2 and no hidden overhead; this is load-bearing for the central simulation claim.

    Authors: The phrase '2-linear time' is meant to indicate that each TM transition is realized by at most two CA steps because the encoding places the state symbol and tape symbol in adjacent cells that update in parallel. We acknowledge that neither a precise definition of the time measure nor an explicit accounting of the correspondence appears in the text. The revised version will define the time measure, state the exact correspondence, and derive the factor of two with a short table or diagram showing the per-step overhead. revision: yes

  3. Referee: The three concrete examples (binary sum, Rule 110, universal reversible TM) demonstrate spatial dynamics but do not establish the general claim, as they leave open the possibility of simulation divergence or extra overhead on other TMs not covered by the cases.

    Authors: The three examples were selected to illustrate distinct classes of computation, yet we recognize that concrete instances alone cannot rule out divergence or hidden overhead for TMs outside these cases. The lemma added in response to the first comment will be stated for arbitrary TMs and will therefore close this gap; the examples will then serve only as illustrations rather than as the sole support for the general result. revision: yes

Circularity Check

0 steps flagged

No circularity: direct construction with no self-referential reductions

full rationale

The manuscript presents a conversion algorithm from arbitrary Turing machines to 1D cellular automata and illustrates it on three concrete examples (binary sum, rule 110, universal reversible TM). No equations, fitted parameters, predictions of derived quantities, or load-bearing self-citations appear in the provided text. The central claim is a constructive statement whose validity rests on the algorithm itself rather than on any reduction to its own outputs or prior self-referential results. This is the normal case of a self-contained algorithmic derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; all such elements remain unknown.

pith-pipeline@v0.9.0 · 5608 in / 992 out tokens · 23994 ms · 2026-05-25T01:26:49.822389+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Andrew Adamatzky (Ed.). 2002. Collision-Based Computing, Springer

    work page 2002

  2. [2]

    Edwin R. Banks. 1971. Information and transmission in cellular automata, PhD Dissertion, Cambridge, MA, MIT

    work page 1971

  3. [3]

    Edward F. Codd. 1968. Cellular Automata, Academic Press, Inc. New York and London

    work page 1968

  4. [4]

    Matthew Cook (2004) Universality in Elementary Cellular Automata,Com- plex Systems, 15(1), 1–40

    work page 2004

  5. [5]

    Martin Davis (Ed.). 1965. The Undecidable, Raven Press Books

    work page 1965

  6. [6]

    Martin Gardner. 1970. Mathematical Games - The fantastic combinations of John H. Conway’s new solitaire game Life, Scientific American , 223, 120–123. 13 Table 8: Set of rules defined for CUR to simulate M. u(x) f (u(x)) equivalentM transitions Z1 Z2 q′ 1 q1 - Z1 Z2 q′ 2 q2 - Z1 Z2 q′ 3 q3 - Z1 Z2 q′ 6 q6 - Z1 Z2 q′ 9 q9 - Z1 Z2 q′ 13 q13 - Z1 Z2 q′ 14 q14 ...

    work page 1970

  7. [7]

    Anthony J. G. Hey. 1998. Feynman and computation: exploring the limits of computers, Perseus Books

    work page 1998

  8. [8]

    Hopcroft and Jeffrey D

    John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory Languages, and Computation, Reading: Addison-Wesley Publishing Company

    work page 1979

  9. [9]

    Kristian Lindgren and Mats G. Nordahl. 1990. Universal Computation in Simple One-Dimensional Cellular Automata, Complex Systems, 4, 229–318

    work page 1990

  10. [10]

    Mart´ ınez, Andrew Adamatzky, Kenichi Morita, and Maurice Margenstern

    Genaro J. Mart´ ınez, Andrew Adamatzky, Kenichi Morita, and Maurice Margenstern. 2010. Computation with competing patterns in Life-like au- tomaton, In: Game of Life Automata, A. Adamatzky (Ed.), Springer, chap- ter 27, pages 547–572

    work page 2010

  11. [11]

    Mart´ ınez, Andrew Adamatzky, and Kenichi Morita

    Genaro J. Mart´ ınez, Andrew Adamatzky, and Kenichi Morita. 2018. Log- ical Gates via Gliders Collisions, In: Reversibility and Universality , A. Adamatzky (Ed.), Springer, chapter 9, 199–220

    work page 2018

  12. [12]

    Mart´ ınez, Andrew Adamatzky, Christopher R

    Genaro J. Mart´ ınez, Andrew Adamatzky, Christopher R. Stephens, and Alejandro F. Hoeflich. 2011. Cellular automaton supercolliders, Interna- tional Journal of Modern Physics C , 22(4), 419–439

    work page 2011

  13. [13]

    McIntosh

    Harold V. McIntosh. 1999. Rule 110 as it relates to the presence of gliders, http://delta.cs.cinvestav.mx/~mcintosh/comun/RULE110W/ rule110.pdf, accessed July 2018

    work page 1999

  14. [14]

    McIntosh

    Harold V. McIntosh. 2009. One Dimensional Cellular Automata , Luniver Press

    work page 2009

  15. [15]

    McIntosh and Gerardo Cisneros

    Harold V. McIntosh and Gerardo Cisneros. 1990. The programming lan- guages REC and convert, SIGPLAN Notices, 25(7), 81–94

    work page 1990

  16. [16]

    Marvin Minsky. 1967. Computation: Finite and Infinite Machines , Prentice Hall

    work page 1967

  17. [17]

    Mart´ ınez and Kenichi Morita

    Genaro J. Mart´ ınez and Kenichi Morita. 2018. Conservative Computing in a One-dimensional Cellular Automaton with Memory, Journal of Cellular Automata, 13(4), 325–346

    work page 2018

  18. [18]

    Mart´ ınez, Kenichi Morita, Andrew Adamatzky, and Maurice Margenstern

    Genaro J. Mart´ ınez, Kenichi Morita, Andrew Adamatzky, and Maurice Margenstern. 2010. Majority adder implementation by competing patterns in Life-like rule B2/S2345, Lecture Notes in Computer Science , 6079, 93– 104

    work page 2010

  19. [19]

    Mart´ ınez, Harold V

    Genaro J. Mart´ ınez, Harold V. McIntosh, and Juan C. S. T. Mora. 2006. Gliders in Rule 110, International Journal of Unconventional Computing , 2(1), 1–49. 17

    work page 2006

  20. [20]

    Mart´ ınez, Harold V

    Genaro J. Mart´ ınez, Harold V. McIntosh, Juan C. S. T. Mora, and Sergio V. Ch. Vergara. 2011. Reproducing the cyclic tag system developed by Matthew Cook with Rule 110 using the phases f 1 1, Journal of Cellular Automata, 6(2-3), 121–161

    work page 2011

  21. [21]

    Kenichi Morita and Yoshikazu Yamaguchi. 2007. A Universal Reversible Turing Machine, Lecture Notes in Computer Science , 4664, 90–98

    work page 2007

  22. [22]

    Vichniac (1986) Cellular-Automata Supercomputers for Fluid Dynamics Modeling, Phys- ical Review Letters, 56(16), 1694–1696

    Norman Margolus, Tommaso Toffoli, and Gerard Y. Vichniac (1986) Cellular-Automata Supercomputers for Fluid Dynamics Modeling, Phys- ical Review Letters, 56(16), 1694–1696

    work page 1986

  23. [23]

    Paul Rendell. 2016. Turing Machine Universality of the Game of Life , Springer

    work page 2016

  24. [24]

    Claude E. Shannon. 1956. A Universal Turing Machine with Two Internal States, Automata Studies, Princeton University Press, 157–165

    work page 1956

  25. [25]

    Smith III

    Alvy R. Smith III. 1971. Simple computation-universal cellular spaces, J. of the Assoc. for Computing Machinery , 18, 339–353

    work page 1971

  26. [26]

    Alan M. Turing. 1936. On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London mathematical society , 2(1), 230–265

    work page 1936

  27. [27]

    John von Neumann. 1966. Theory of Self-reproducing Automata (edited and completed by A. W. Burks), University of Illinois Press, Urbana and London

    work page 1966

  28. [28]

    Stephen Wolfram. 1984. Universality and complexity in cellular automata, Physica D, 10, 1–35

    work page 1984

  29. [29]

    Stephen Wolfram. 1988. Cellular Automata Supercomputing, In: High Speed Computing: Scientific Applications and Algorithm Design, R. B. Wil- helmson (Ed.), University of Illinois Press, pages 40–48

    work page 1988

  30. [30]

    Stephen Wolfram. 2002. A New Kind of Science , Wolfram Media, Inc., Champaign, Illinois

    work page 2002

  31. [31]

    Hector Zenil. 2012. On the Dynamic Qualitative Behaviour of Universal Computation, Complex Systems, 20(3), 265–278. 18

    work page 2012