A Billiard Ball as a Universal Computation Machine
hubie writes:
I came across a very interesting social media post by John Carlos Baez about a paper published a few weeks ago that showed you can build a universal computation machine using a single billiard ball on a carefully crafted table. According to one of the paper's authors (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 that established the idea of "Conservative Logic," which was also mentioned by Richard Feynman in his Feynman Lectures on Computation, 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.
Read more of this story at SoylentNews.