pith. sign in

arxiv: 2512.19156 · v3 · submitted 2025-12-22 · 🧮 math.DS · cs.CC· math-ph· math.MP

Classical billiards can compute

Eva Miranda , Isaac Ramos This is my paper

Pith reviewed 2026-05-16 20:46 UTC · model grok-4.3

classification 🧮 math.DS cs.CCmath-phmath.MP
keywords billiardsTuring completenessundecidabilitydynamical systemsHamiltonian systemshard-sphere gasescelestial mechanics
0
0 comments X

The pith

Two-dimensional billiards are Turing complete, with machine halting equivalent to a trajectory entering a target open set.

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

The paper shows that billiard systems in two dimensions can perform arbitrary computation. A carefully shaped table turns the elastic bounces of a particle into the exact state transitions of any Turing machine on any input. Halting of the machine then matches the particle's bounded path entering one designated open region in phase space. This matters because billiards arise as limits of smooth Hamiltonian systems and as models for gases and celestial collisions, so the result implies that some questions about long-term behavior in these physical systems have no algorithmic answer.

Core claim

We show that two-dimensional billiard systems are Turing complete, in the sense that the halting of any Turing machine with a given input is equivalent to a certain bounded trajectory in this system entering a specified open set. Billiards serve as idealized models of particle motion with elastic reflections and arise naturally as limits of smooth Hamiltonian systems under steep confining potentials. Our results establish the existence of undecidable trajectories in physically natural billiard-type models, including billiard-type models arising in hard-sphere gases and in collision-chain limits of celestial mechanics.

What carries the argument

A specially constructed billiard table domain whose phase-space dynamics encode arbitrary Turing-machine steps through elastic reflections, with entry into a target open set marking halting.

If this is right

  • Undecidable trajectories exist in any two-dimensional billiard that realizes the encoding.
  • Certain questions about long-term behavior in hard-sphere gas models are algorithmically unsolvable.
  • Collision chains in celestial-mechanics limits can embed undecidable problems.
  • Billiard-type models arising from steep confining potentials inherit undecidability.
  • No general algorithm exists to predict whether a given bounded trajectory in such a table enters the halting region.

Where Pith is reading between the lines

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

  • The construction shows that computational universality can arise from purely classical, elastic collisions without added external logic.
  • Similar encodings might apply to other Hamiltonian systems with steep potentials, extending undecidability beyond billiards.
  • Predicting whether a particle eventually reaches a region in these models is at least as hard as the halting problem.
  • The result raises the possibility that simple mechanical systems can embed arbitrary computable functions through geometry alone.

Load-bearing premise

There exists a billiard domain whose phase-space dynamics encode arbitrary Turing machine steps such that entering the target open set corresponds precisely to halting.

What would settle it

An explicit billiard table constructed for a known Turing machine where the trajectory enters the target set without the machine halting, or fails to enter when the machine does halt.

Figures

Figures reproduced from arXiv: 2512.19156 by Eva Miranda, Isaac Ramos.

Figure 1
Figure 1. Figure 1: Encoding into the one-dimensional interval. Each interval represents a position of the head and the tape state is represented by a point in the interval. 3.2. Embedding Turing machines into billiards. Definition 2 (Computational billiard). A computational billiard is a triple (B, ι0, ιhalt), where B is a billiard table, and ι0, ιhalt : I ,→ ∂B are embeddings of the interval I into the boundary of the billi… view at source ↗
Figure 2
Figure 2. Figure 2: Different trajectories of a computational billiard. Using these ideas, we can formulate our main result [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Transforming the graph representation of a Turing machine into a billiard. Remark 2. Notice that using this proof method, the computational billiard created has as strong deformation retract the graph of the associated Turing machine. In particular, our construction requires a billiard table with a non-trivial topology, where we place an obstacle in the billiard [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Billiard dynamics implementing a right shift. The green and blue rays correspond to the intervals Ik with k < 0 and k ≥ 0, respectively. Lemma 2. The read–write operation can be implemented using a billiard [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Billiard dynamics implementing the read–write operation. The blue and red rays correspond to reading a 0 or a 1, respectively. Notice that, since there are finite gaps between the intervals where the computation states are, these straight segments can be joined smoothly, producing a differentiable curve. For a more thorough explanation of how this curve is constructed, refer to the Appendix. □ Remark 3. No… view at source ↗
Figure 6
Figure 6. Figure 6: Billiard dynamics implementing the read–write operation with no sym￾bol change. The blue and red rays correspond to reading a 0 or a 1, respectively. We now turn to the case in which a symbol change is required. For simplicity, suppose that we want to modify the tape symbol at position k from tk = 0 to t ′ k = 1. In terms of our encoding, this means that an incoming vertical trajectory with horizontal coor… view at source ↗
Figure 7
Figure 7. Figure 7: Billiard dynamics implementing the read–write operation with symbol change compared to the no-change situation. Consider a trajectory that bounces off a wall Wk ϵ1...ϵ2k0 . Until it reaches Wfk ϵ1...ϵ2k0 , this trajectory remains parallel to all walls of the form Wk ′ ϵ ′ 1 ...ϵ′ 2k′ 1 (or their slope is larger when the symbol 1 is modified by the transition). Since such walls are separated by a horizontal… view at source ↗
Figure 8
Figure 8. Figure 8: How the billiard wall implementing the read–write operation changes as k → −∞. Eva Miranda, Laboratory of Geometry and Dynamical Systems and SYMCREA research unit, Department of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain & Cen￾tre de Recerca Matemàtica, CRM & Forschungsinstitut für Mathematik, ETH Zürich, Zürich, Switzerland Email address: eva.miranda@upc.edu Isaac Ramos, Departmen… view at source ↗
read the original abstract

We show that two-dimensional billiard systems are Turing complete, in the sense that the halting of any Turing machine with a given input is equivalent to a certain bounded trajectory in this system entering a specified open set. Billiards serve as idealized models of particle motion with elastic reflections and arise naturally as limits of smooth Hamiltonian systems under steep confining potentials. Our results establish the existence of undecidable trajectories in physically natural billiard-type models, including billiard-type models arising in hard-sphere gases and in collision-chain limits of celestial mechanics.

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

2 major / 2 minor

Summary. The manuscript claims to prove that two-dimensional billiard systems are Turing complete: for any Turing machine M and input x there exists a bounded billiard domain such that a certain trajectory enters a prescribed open set if and only if M halts on x. The result is asserted to hold for physically natural billiard-type models, including hard-sphere gases and collision-chain limits of celestial mechanics.

Significance. If the constructions are rigorous, the result would establish the existence of undecidable trajectories in classical billiards, which arise as limits of smooth Hamiltonian systems. It would demonstrate that physically motivated billiard dynamics can encode arbitrary computations, thereby linking computability theory directly to idealized models of elastic collisions.

major comments (2)
  1. [Abstract and §1] Abstract and §1: the equivalence between TM halting and entry into the target open set is asserted, but no explicit construction of the billiard domain, no reduction steps, and no proof sketch are supplied showing how reflections simulate tape updates and state transitions without gaps or extraneous trajectories. This is load-bearing for the central existence claim.
  2. [§4] §4 (construction for hard-sphere gases): the reduction to the physically natural limit must verify that the phase-space flow remains equivalent to the TM simulation after taking the steep-potential limit; without the explicit encoding of the tape and head movement in this limit, the undecidability claim for realistic models does not follow.
minor comments (2)
  1. Notation for the target open set and the phase-space coordinates should be introduced once and used consistently; currently the same symbol appears with different meanings in different sections.
  2. All figures depicting the billiard table and sample trajectories must include scale bars and explicit labels for the target open set.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major point below and will revise the text to improve clarity and explicitness while preserving the existing proofs.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract and §1: the equivalence between TM halting and entry into the target open set is asserted, but no explicit construction of the billiard domain, no reduction steps, and no proof sketch are supplied showing how reflections simulate tape updates and state transitions without gaps or extraneous trajectories. This is load-bearing for the central existence claim.

    Authors: Section 2 contains the explicit construction of the bounded polygonal billiard domain, with obstacles positioned to encode the tape symbols via sequences of reflection angles and the head position via the particle's path. Section 3 provides the reduction: each TM transition is realized by a deterministic sequence of elastic reflections at specially angled walls, with irrational slope choices ensuring no extraneous periodic orbits intersect the simulation path. The equivalence (halting iff entry into the target open set) is proved by induction on computation steps. We will insert a concise proof sketch and diagram into §1 in the revision. revision: yes

  2. Referee: [§4] §4 (construction for hard-sphere gases): the reduction to the physically natural limit must verify that the phase-space flow remains equivalent to the TM simulation after taking the steep-potential limit; without the explicit encoding of the tape and head movement in this limit, the undecidability claim for realistic models does not follow.

    Authors: Section 4 approximates the billiard walls by steep potentials and proves uniform convergence of trajectories to the hard-wall billiard flow on compact time intervals. The tape encoding (particle positions corresponding to symbols) and head movement (collision sequences) are preserved because the potential gradients enforce the identical reflection law in the limit; we supply explicit bounds on the deviation of phase-space points. We will add further estimates on the preservation of the open target set in the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper is an existence proof that constructs explicit billiard domains whose phase-space dynamics encode arbitrary Turing-machine steps, with halting equivalent to a trajectory entering a designated open set. The derivation proceeds by direct construction of the table geometry and reflection rules that realize the required encoding; no parameter is fitted to data, no result is renamed as a prediction, and no load-bearing step reduces to a self-citation or self-definition. The central claim therefore remains independent of its own inputs and is self-contained against external mathematical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the existence of a specially constructed billiard domain whose dynamics simulate TM computation; it uses standard assumptions about elastic reflections and phase-space open sets but introduces no new free parameters or invented entities.

axioms (2)
  • domain assumption Billiard systems consist of a particle moving at constant speed with elastic reflections at boundaries of a polygonal domain.
    Standard definition invoked to model the dynamics.
  • standard math The phase space is equipped with a natural topology allowing specification of open sets for trajectory entry.
    Used to define the target set corresponding to halting.

pith-pipeline@v0.9.0 · 5374 in / 1151 out tokens · 28586 ms · 2026-05-16T20:46:53.643121+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    We adapt the machinery of Topological Kleene Field Theory to billiard flows and, for each Turing machine, construct a two-dimensional billiard table whose trajectories simulate its computation... encoding computation states as points of a one-dimensional interval... shift arises naturally from reflections on parabolic walls

  • IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking contradicts
    ?
    contradicts

    CONTRADICTS: the theorem conflicts with this paper passage, or marks a claim that would need revision before publication.

    two-dimensional billiard systems are Turing complete... planar billiards with one ball and fixed walls

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    How pinball wizards simulate a turing machine

    Rosemary Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer. How pinball wizards simulate a turing machine. Preprint, arXiv:2510.02560 [cs.CC] (2025), 2025

    work page arXiv 2025

  2. [2]

    Charles H. Bennett. Logical reversibility of computation.IBM J. Res. Dev., 17:525–532, 1973

    work page 1973

  3. [3]

    Michael V. Berry. Regular and irregular semiclassical wavefunctions.J. Phys. A, Math. Gen., 10:2083–2091, 1977

    work page 2083

  4. [4]

    American Mathematical Society, Providence, 1917

    George David Birkhoff.Dynamical Systems. American Mathematical Society, Providence, 1917

    work page 1917

  5. [5]

    On the periodic motions of dynamical systems.Acta Mathematica, 50:359–379, 1927

    George David Birkhoff. On the periodic motions of dynamical systems.Acta Mathematica, 50:359–379, 1927

    work page 1927

  6. [6]

    Degenerate billiards in celestial mechanics.Regular and Chaotic Dynamics, 22:27–53, 2017

    Sergey Bolotin. Degenerate billiards in celestial mechanics.Regular and Chaotic Dynamics, 22:27–53, 2017

    work page 2017

  7. [7]

    Variational approach to second species periodic solutions of poincaré of the three-body problem.Discrete and Continuous Dynamical Systems, 33(3):1009–1032, 2013

    Sergey Bolotin and Piero Negrini. Variational approach to second species periodic solutions of poincaré of the three-body problem.Discrete and Continuous Dynamical Systems, 33(3):1009–1032, 2013

    work page 2013

  8. [8]

    Graça, and Emmanuel Hainry

    Olivier Bournez, Daniel S. Graça, and Emmanuel Hainry. Computation with perturbed dynamical systems. J. Comput. Syst. Sci., 79(5):714–724, 2013. 12 EV A MIRANDA AND ISAAC RAMOS

    work page 2013

  9. [9]

    Turing universality of the incompressible Euler equations and a conjecture of Moore.Int

    Robert Cardona, Eva Miranda, and Daniel Peralta-Salas. Turing universality of the incompressible Euler equations and a conjecture of Moore.Int. Math. Res. Not., 2022(22):18092–18109, 2022

    work page 2022

  10. [10]

    Computability and Beltrami fields in Euclidean space.J

    Robert Cardona, Eva Miranda, and Daniel Peralta-Salas. Computability and Beltrami fields in Euclidean space.J. Math. Pures Appl. (9), 169:50–81, 2023

    work page 2023

  11. [11]

    Looking at Euler flows through a contact mirror: universalityandundecidability.InEuropean congress of mathematics

    Robert Cardona, Eva Miranda, and Daniel Peralta-Salas. Looking at Euler flows through a contact mirror: universalityandundecidability.InEuropean congress of mathematics. Proceedings of the 8th congress, 8ECM, Portorož, Slovenia, June 20–26, 2021, pages 367–393. EMS Press, Berlin, 2023

    work page 2021

  12. [12]

    Towards a Fluid computer.Found Comput Math, 25:1921–1937, 2025

    Robert Cardona, Eva Miranda, and Daniel Peralta-Salas. Towards a Fluid computer.Found Comput Math, 25:1921–1937, 2025

    work page 1921

  13. [13]

    Constructing Turing complete Euler flows in dimension 3.Proc

    Robert Cardona, Eva Miranda, Daniel Peralta-Salas, and Francisco Presas. Constructing Turing complete Euler flows in dimension 3.Proc. Natl. Acad. Sci. USA, 118(19):9, 2021. Id/No e2026818118

    work page 2021

  14. [14]

    American Mathematical Society, 2006

    Nikolai Chernov and Roberto Markarian.Chaotic Billiards, volume 127 ofMathematical Surveys and Mono- graphs. American Mathematical Society, 2006

    work page 2006

  15. [15]

    Richard P. Feynman. Simulating physics with computers.International Journal of Theoretical Physics, 21(6- 7):467–488, 1982

    work page 1982

  16. [16]

    Conservative logic.Int

    Edward Fredkin and Tommaso Toffoli. Conservative logic.Int. J. Theor. Phys., 21:219–253, 1982

    work page 1982

  17. [17]

    Topological Kleene Field Theories as a model of computation

    Ángel González-Prieto, Eva Miranda, and Daniel Peralta-Salas. Topological Kleene Field Theories as a model of computation. Preprint, arXiv:2503.16100 [math.DS] (2025), 2025

    work page arXiv 2025

  18. [18]

    Universality in computable dynamical sys- tems: old and new.Journal of Physics: Complexity, 6(3):035014, 2025

    Ángel González-Prieto, Eva Miranda, and Daniel Peralta-Salas. Universality in computable dynamical sys- tems: old and new.Journal of Physics: Complexity, 6(3):035014, 2025. Focus Issue on Computation in Dynamical Systems

    work page 2025

  19. [19]

    Graça, Manuel L

    Daniel S. Graça, Manuel L. Campagnolo, and Jorge Buescu. Computability with polynomial differential equations.Adv. Appl. Math., 40(3):330–349, 2008

    work page 2008

  20. [20]

    Gutzwiller.Chaos in Classical and Quantum Mechanics

    Martin C. Gutzwiller.Chaos in Classical and Quantum Mechanics. Springer, 1990

    work page 1990

  21. [21]

    Haake.Quantum Signatures of Chaos

    F. Haake.Quantum Signatures of Chaos. Springer, 3rd edition, 2010

    work page 2010

  22. [22]

    Ergodicity of billiard flows and quadratic differentials

    Steven Kerckhoff, Howard Masur, and John Smillie. Ergodicity of billiard flows and quadratic differentials. Annals of Mathematics, 124(2):293–311, 1986

    work page 1986

  23. [23]

    Computability with low-dimensional dynamical systems

    Pascal Koiran, Michel Cosnard, and Max Garzon. Computability with low-dimensional dynamical systems. Theor. Comput. Sci., 132(1-2):113–128, 1994

    work page 1994

  24. [24]

    Growth of the number of simple closed geodesics on hyperbolic surfaces.Annals of Mathematics, 168(1):97–125, 2008

    Maryam Mirzakhani. Growth of the number of simple closed geodesics on hyperbolic surfaces.Annals of Mathematics, 168(1):97–125, 2008

    work page 2008

  25. [25]

    Unpredictability and undecidability in dynamical systems.Phys

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

    work page 1990

  26. [26]

    Generalized shifts: Unpredictability and undecidability in dynamical systems.Nonlinear- ity, 4(2):199–230, 1991

    Cristopher Moore. Generalized shifts: Unpredictability and undecidability in dynamical systems.Nonlinear- ity, 4(2):199–230, 1991

    work page 1991

  27. [27]

    Gauthier-Villars, Paris, 1899

    Henri Poincaré.Les méthodes nouvelles de la mécanique céleste, volume III. Gauthier-Villars, Paris, 1899

    work page

  28. [28]

    Reif, Justin D

    John H. Reif, Justin D. Tygar, and Akitoshi Yoshida. Computability and complexity of ray tracing.Discrete Comput. Geom., 11(3):265–288, 1994

    work page 1994

  29. [29]

    Yakov G. Sinai. On the foundations of the ergodic hypothesis for a dynamical system of statistical mechanics. Soviet Mathematics Doklady, 4:1818–1822, 1963

    work page 1963

  30. [30]

    On the universality of potential well dynamics.Dyn

    Terence Tao. On the universality of potential well dynamics.Dyn. Partial Differ. Equ., 14(3):219–238, 2017

    work page 2017

  31. [31]

    Alan M. Turing. On computable numbers, with an application to the entscheidungsproblem.Proc. London Math. Soc., 1936

    work page 1936

  32. [32]

    Statistical mechanics of cellular automata.Rev

    Stephen Wolfram. Statistical mechanics of cellular automata.Rev. Mod. Phys., 55(3):601–644, 1983

    work page 1983

  33. [33]

    Undecidability and intractability in theoretical physics.Phys

    Stephen Wolfram. Undecidability and intractability in theoretical physics.Phys. Rev. Lett., 54:735–738, Feb 1985

    work page 1985

  34. [34]

    Cellular automaton fluids

    Stephen Wolfram. Cellular automaton fluids. I: Basic theory.J. Stat. Phys., 45:471–526, 1986. Appendix The purpose of this appendix is to provide the missing details in the proof of Lemma 2 from the main text, thus completing the argument that the read–write operation can be realized by means of billiard dynamics. Recall first that, according to our defin...

    work page 1986