Classical billiards can compute (2d billiard systems are Turing complete)
29 points by nabla9
by QuadmasterXLII
1 subcomments
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
by bsima
0 subcomment
i knew there was a good reason i like playing pool so much
Hacker News