Two-dimensional billiards are Turing complete

• 成果类型: Article
• 署名作者: Miranda, Eva; Ramos, Isaac
• 署名单位: Centre de Recerca Matematica (CRM); Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
• ISSN/ISSBN: 0027-8424; 1091-6490
• DOI: 10.1073/pnas.2614500123
• 发表日期: 2026-09-15
• 页码: e2614500123
• 关键词: billiards; Undecidable; Turing complete; dynamical systems; halting problem; Computability; undecidability; UNPREDICTABILITY

摘要

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.