Classical billiards can compute (2d billiard systems are Turing complete)(arxiv.org)
26 pointsby nabla910 hours ago2 comments
  • QuadmasterXLII5 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
    • _alternator_4 hours ago
      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.

      • QuadmasterXLII3 hours ago
        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
  • bsima5 hours ago
    i knew there was a good reason i like playing pool so much