SoylentNews

hubie [soylentnews.org] writes:

I came across a very interesting social media post by John Carlos Baez [mathstodon.xyz] about a paper published a few weeks ago that showed you can build a universal computation machine [wikipedia.org] using a single billiard ball on a carefully crafted table. According to one of the paper's authors [bsky.app] (Eva Miranda):

With Isaac Ramos, we show that 2D billiard systems are Turing complete, implying the existence of undecidable trajectories in physically natural models from hard-sphere gases to celestial mechanics.
Determinism ≠ predictability.

From Baez:

More precisely: you can create a computer that can run any program, using just a single point moving frictionlessly in a region of the plane and bouncing off the walls elastically.

Since the halting problem is undecidable, this means there are some yes-or-no questions about the eventual future behavior of this point that cannot be settled in a finite time by any computer program.

This is true even though the point's motion is computable to arbitrary accuracy for any given finite time. In fact, since the methodology here does *not* exploit the chaos that can occur for billiards on certain shaped tables, it's not even one of those cases where the point's motion is computable in principle but your knowledge of the initial conditions needs to be absurdly precise.

Achieving Turing completeness using billiards goes back to the early 80s with a paper by Fredkin and Toffoli [princeton.edu] that established the idea of "Conservative Logic," which was also mentioned by Richard Feynman in his Feynman Lectures on Computation [upc.edu], but that system used the interactions of multiple billiard balls whereas this paper shows you only need one (if you carefully layout the edges of your table).

The Baez link has some very interesting comments, including from Eva Miranda.

Original Submission