Classical billiards can compute (2d billiard systems are Turing complete)
arxiv.org28 points by nabla9 17 hours ago
28 points by nabla9 17 hours ago
This is a really cool result! It's computation in a single ball bouncing around a 2-D container, with the infinite state needed encoded in infinite digits of the real number coordinates of the ball (and balls velocity.) Am I reading correctly that the boundary of the billiard table is fractal, with infinite complexity, but the complexity is simple in some sense? Otherwise, a fractal wall encoding a look-up-table of halt/doesn't halt would also do turing computation (better even!) but the paper seems less trivial than this
Embedding state in a real number, and calling it a “length” is a common trick to show that a physical system is TC. Unfortunately, the abstraction (length<->real number) suffers from numerous real-world issues that typically renders any implementation impossible.
I’m not even talking impractical; real numbers are simply too powerful to be resolved in the physical world. Unless you spend a ton of effort talking about quantizing and noise, you are very, very far from a realizable computer.
I think it outside of implementability, it provides a nice proof that no algorithm can answer questions like “is the trajectory of this ball in this billiard eventually periodic.” Of course it (if I am reading correctly) leaves open that an algorithm could exist assuming the wall isn’t fractal
i knew there was a good reason i like playing pool so much