pith. sign in

arxiv: 2404.07288 · v3 · submitted 2024-04-10 · 🧮 math.DS · cs.CC

Topological entropy of Turing complete dynamics

Renzo Bruera , Robert Cardona , Eva Miranda , Daniel Peralta-Salas , Ville Salo This is my paper

Pith reviewed 2026-05-24 02:00 UTC · model grok-4.3

classification 🧮 math.DS cs.CC
keywords topological entropyTuring completenessdynamical systemsbranching Turing machinessymbolic dynamicschaosuniversalityzero entropy
0
0 comments X

The pith

Universal Turing machines can be constructed with zero topological entropy.

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

The paper examines the connection between a system's ability to perform any computation and its level of chaos as quantified by topological entropy. It first shows that branching Turing machines, a broad class covering most known universal examples, always exhibit positive topological entropy. This implies that certain Turing complete dynamical systems using continuous encodings must be chaotic. On the other hand, the authors build universal Turing machines that achieve zero topological entropy and even zero speed, establishing that universality and chaos can occur independently in symbolic settings.

Core claim

Branching Turing machines have positive topological entropy, so any Turing complete dynamics with a continuous encoding that simulates a universal branching machine is chaotic. At the same time, universal Turing machines with zero topological entropy and zero speed can be constructed, showing that chaos and universality are independent at the symbolic level.

What carries the argument

Branching Turing machines, a class that includes most known universal Turing machines and forces positive topological entropy, set against specially constructed universal machines that achieve zero entropy.

Load-bearing premise

Branching Turing machines form a natural class that includes most universal examples, and the continuous encoding condition holds when moving from these machines to the dynamical systems.

What would settle it

A universal branching Turing machine with zero topological entropy, or the failure of the zero-entropy universal machine constructions to simulate all computations, would disprove the central claims.

Figures

Figures reproduced from arXiv: 2404.07288 by Daniel Peralta-Salas, Eva Miranda, Renzo Bruera, Robert Cardona, Ville Salo.

Figure 1
Figure 1. Figure 1: Transition table of UTM(6, 4) [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Transition table of W UTM(6, 2) [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Graph of W U6,2 for ε = +1. Example 2. The universal Turing machine UTM(15, 2) in [28] is another ex￾ample of universal Turing machine that is not strongly regular, but it is regular. Looking at the transition table [28, [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
read the original abstract

We explore the relationship between Turing completeness and topological entropy of dynamical systems. We first prove that a natural class of Turing machines that we call "branching Turing machines" (which includes most of the known examples of universal Turing machines) has positive topological entropy. Motivated by the recent construction of Turing complete Euler flows, we deduce that any Turing complete dynamics with a continuous encoding that simulates a universal branching machine is chaotic. On the other hand, we show that, unexpectedly, universal Turing machines with zero topological entropy (and even zero speed) can be constructed, unveiling the independence of chaos and universality at the symbolic level.

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

0 major / 3 minor

Summary. The manuscript explores the relationship between Turing completeness and topological entropy. It defines a class of 'branching Turing machines' (containing most known universal examples), proves that their associated shift spaces have positive topological entropy, and deduces that any Turing-complete dynamics with a continuous encoding that simulates a universal branching machine must be chaotic. It then supplies an explicit, parameter-free construction of a universal Turing machine whose configuration space has zero topological entropy (and zero speed), establishing independence of universality and chaos at the symbolic level.

Significance. If the constructions and entropy calculations hold, the work supplies a clean separation between computational universality and positive topological entropy, with both a positive-entropy result for a broad natural class and a zero-entropy universal example. The explicit, self-contained nature of the branching-machine definition, the list of standard universal machines inside the class, and the separate zero-entropy construction are strengths that make the independence claim falsifiable and directly verifiable.

minor comments (3)
  1. [§2] §2 (definition of branching Turing machines): the list of standard universal machines included in the class is helpful, but a short table or explicit citation for each example would make the claim that the class is 'natural' easier to check.
  2. [Corollary 1.3] The continuous-encoding hypothesis is stated explicitly for the chaotic-dynamics corollary; a one-sentence reminder in the statement of the corollary itself would prevent any reader from overlooking that the zero-entropy existence result does not rely on it.
  3. [Theorem 1.4] The zero-speed claim for the constructed universal machine is strong; a brief remark on how speed is measured (e.g., reference to a standard definition) would clarify the statement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the clear summary of our results on branching Turing machines and the zero-entropy universal example, as well as the recommendation for minor revision. No major comments are listed in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines branching Turing machines explicitly, proves they have positive topological entropy via direct argument on their shift spaces, and separately constructs a universal TM with zero entropy (and zero speed) using a parameter-free construction. The continuous-encoding hypothesis is stated only for the chaotic-dynamics corollary and is not used in the zero-entropy existence claim. No equation or step reduces by construction to a fitted input, self-definition, or load-bearing self-citation chain; both directions rely on standard definitions of topological entropy and Turing completeness. The derivation chain is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The paper relies on standard definitions of topological entropy and Turing machines from prior literature, plus the newly introduced class of branching Turing machines whose properties are proved rather than postulated without evidence.

axioms (2)
  • standard math Topological entropy is a well-defined invariant for the symbolic dynamical systems arising from Turing machines.
    Invoked throughout the abstract as the central quantity.
  • domain assumption A continuous encoding exists that allows simulation of branching machines by the target dynamical systems.
    Required for the deduction that Turing-complete dynamics are chaotic.
invented entities (1)
  • branching Turing machines no independent evidence
    purpose: A subclass of Turing machines that includes most universal examples and is proved to have positive topological entropy.
    Defined in the paper to enable the positive-entropy theorem; no independent evidence outside the constructions.

pith-pipeline@v0.9.0 · 5632 in / 1263 out tokens · 37280 ms · 2026-05-24T02:00:41.370657+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

35 extracted references · 35 canonical work pages · 1 internal anchor

  1. [1]

    Adler, A.G

    R.L. Adler, A.G. Konheim, M.H. McAndrew. Topological entropy. Trans. Amer. Math. Soc. 114 (1965), 309–319

    work page 1965

  2. [2]

    V. D. Blondel, J. Cassaigne, C. Nichitiu. On the presence of periodic configurations in Turing machines and in counter machines . Theor. Comput. Sci. 289 (2002), 573–590

    work page 2002

  3. [3]

    R. Berger. The undecidability of the domino problem . Mem. Amer. Math. Soc. 66 (1966), 1–72

    work page 1966

  4. [4]

    R. Bowen. Entropy for groups endomorphisms and homogeneous spaces . Trans. Amer. Math. Soc. 153 (1971), 401–414

    work page 1971

  5. [5]

    Cardona, E

    R. Cardona, E. Miranda, D. Peralta-Salas. Turing universality of the incompressible Euler equations and a conjecture of Moore . Int. Math. Res. Notices 2022 (2022), 18092–18109

    work page 2022

  6. [6]

    Cardona, E

    R. Cardona, E. Miranda, D. Peralta-Salas. Computability and Beltrami fields in Euclidean space. J. Math. Pures Appl. 169 (2023), 50–81

    work page 2023

  7. [7]

    Cardona, E

    R. Cardona, E. Miranda, D. Peralta-Salas, F. Presas. Constructing Turing complete Euler flows in dimension 3 . Proc. Natl. Acad. Sci. 118 (2021), 19(1–9)

    work page 2021

  8. [8]

    Cardona, E

    R. Cardona, E. Miranda, D. Peralta-Salas, F. Presas. Universality of Euler flows and flexi- bility of Reeb embeddings . Adv. Math. 428 (2023), 109142

    work page 2023

  9. [9]

    Dinaburg

    E. Dinaburg. A connection between various entropy characterizations of dynamical systems. Izv. Akad. Nauk SSSR 35 (1971), 324–366

    work page 1971

  10. [10]

    Gajardo, N

    A. Gajardo, N. Ollinger, R. Torres-Avil´ es. Some undecidable problems about the trace- subshift associated to a Turing machine . Discrete Mathematics & Theoretical Computer Science, 17: Automata, Logic and Semantics (2015)

    work page 2015

  11. [11]

    Gangloff, A

    S. Gangloff, A. Herrera, C. Rojas, M. Sablik. Computability of topological entropy: From general systems to transformations on Cantor sets and the in terval. Discrete Cont. Dyn. Sys. 40 (2020), 4259–4286

    work page 2020

  12. [12]

    On the computability properties of topological entropy: a general approach

    S. Gangloff, A. Herrera, C. Rojas, M. Sablik. On the computability properties of topological entropy: a general approach . Preprint (2019) arXiv:1906.01745

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  13. [13]

    Graca, M.L

    D.S. Graca, M.L. Campagnolo, J. Buescu. Computability with polynomial differential equa- tions. Adv. Appl. Math. 40 (2008), 330–349

    work page 2008

  14. [14]

    Graca, N

    D.S. Graca, N. Zhong. Analytic one-dimensional maps and two-dimensional ordina ry differ- ential equations can robustly simulate Turing machines . Computability 12 (2023), 117–144

    work page 2023

  15. [15]

    P. Hooper. The undecidability of the Turing machine immortality probl em. J. Symbolic Logic 31 (1966), 219–234

    work page 1966

  16. [16]

    E. Jeandel. Computability of the entropy of one-tape Turing machines . 31st International Symposium on Theoretical Aspects of Computer Science, 2014

    work page 2014

  17. [17]

    Katok, B

    A. Katok, B. Hasselblatt, Introduction to the Modern Theory of Dynamical Systems , Cam- bridge Univ. Press, New York, 1995

    work page 1995

  18. [18]

    J. Kari, N. Ollinger. Periodicity and immortality in reversible computing . International Sym- posium on Mathematical Foundations of Computer Science. Be rlin, Heidelberg: Springer Berlin Heidelberg, 2008

    work page 2008

  19. [19]

    Koiran, M

    P. Koiran, M. Cosnard, M. Garzon. Computability with low-dimensional dynamical systems . Theor. Comput. Sci. 132 (1994), 113–128

    work page 1994

  20. [20]

    Koiran, C

    P. Koiran, C. Moore. Closed-form analytic maps in one and two dimensions can simu late universal Turing machines . Theor. Comput. Sci. 210 (1999), 217–223

    work page 1999

  21. [21]

    K˚ urka.On topological dynamics of Turing machines

    P. K˚ urka.On topological dynamics of Turing machines . Theor. Comput. Sci. 174 (1997), 203–216. 18 RENZO BRUERA, ROBERT CARDONA, EV A MIRANDA, AND DANIEL PER ALTA-SALAS

    work page 1997

  22. [22]

    M. Minsky. A 6-symbol 7-state universal Turing machine . MIT Lincoln Laboratory Report G-0027, 1960

    work page 1960

  23. [23]

    M. Minsky. Recursive unsolvability of Post’s problem of “tag” and othe r topics in theory of Turing machines. Ann. of Math. 74 (1961), 437–455

    work page 1961

  24. [24]

    Mitsumatsu, D

    Y. Mitsumatsu, D. Peralta-Salas, R. Slobodeanu. On the existence of critical compatible metrics on contact 3-manifolds. Preprint (2023) arXiv:2311.15833

    work page arXiv 2023

  25. [25]

    C. Moore. Unpredictability and undecidability in dynamical systems . Phys. Rev. Lett. 64 (1990), 2354–2357

    work page 1990

  26. [26]

    C. Moore. Generalized shifts: unpredictability and undecidability in dynamical systems . Non- linearity 4 (1991), 199–230

    work page 1991

  27. [27]

    K. Morita. Theory of reversible computing . Springer Japan, 2017

    work page 2017

  28. [28]

    Neary, D

    T. Neary, D. Woods. Four small universal Turing machines . Fund. Inform. 91 (2009), 123– 144

    work page 2009

  29. [29]

    P. Oprocha. On entropy and Turing machine with moving tape dynamical mod el. Nonlinear- ity 19 (2006) 2475–2487

    work page 2006

  30. [30]

    Rogozhin

    Y. Rogozhin. Small universal Turing machines . Theor. Comput. Sci. 168 (1996), 215–240

    work page 1996

  31. [31]

    C.E. Shannon. A universal Turing machine with two internal states . Automata Studies, pp. 157–165, Ed. C.E. Shannon and J. McCarthy, Princeton Univ. P ress, Princeton, 1956

    work page 1956

  32. [32]

    S. Simpson. Symbolic dynamics: entropy = dimension = complexity . Theor. Comput. Sys. 56 (2015), 527–543

    work page 2015

  33. [33]

    M. Sipser. Introduction to the theory of computation (3rd ed.). International Thomson Pub- lishing, 2012

    work page 2012

  34. [34]

    T. Tao. On the universality of potential well dynamics . Dyn. PDE 14 (2017), 219–238

    work page 2017

  35. [35]

    halting problem barrier

    D. Woods, T. Neary. Small semi-weakly universal Turing machines . In International Con- ference on Machines, Computations, and Universality, Sept ember 2007, pp. 303-315. Berlin, Heidelberg: Springer Berlin Heidelberg. Appendix A. A universal Turing machine with zero topological entropy (by Ville Salo, University of Turku, Finland) The goal of this append...

    work page 2007