Classical billiards can compute (2d billiard systems are Turing complete) | Hacker News Reader

Classical billiards can compute (2d billiard systems are Turing complete)

arxiv.org

32 pointsnabla95 comments

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

> real numbers are simply too powerful to be resolved in the physical world

In a sense "real" numbers are in fact not real at all because they can't physically exist. I think we got it wrong when these numbers were named. What we now call the 'whole' numbers should be called 'real', and vice versa. pi is a whole (in the sense of complete) number because it includes ALL decimal places, but because of infinite precision it can never be realized. 2 is a real (as in it is realizable) number because we can have two of something in reality.

i knew there was a good reason i like playing pool so much

Reply on news.ycombinator.com