Two-dimensional billiards are Turing complete
Abstract
We show that two-dimensional billiard systems can simulate universal Turing machines. Billiards serve as idealized models of particle motion with elastic reflections and arise naturally as limits of smooth Hamiltonian systems under steep confining potentials, and as an exact reformulation of hard-sphere gas dynamics. By invoking the undecidability of the halting problem, originally established by Turing, our results show that undecidable trajectories arise in these physically natural billiard-type models. We further discuss, at the level of analogy, a connection to collision-chain limits in celestial mechanics, where near-collision dynamics exhibit billiard-like symbolic itineraries.
Fields of Study & Subjects
Quantum chaos and dynamical systems
Quantum many-body systems
Control and Stability of Dynamical Systems
Publication details
- Journal / source
- Proceedings of the National Academy of Sciences
- Volume
- 123
- Issue
- 37
- Pages
- e2614500123–e2614500123
- Publication date
- 10 September 2026
- Language
- EN