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.