John Carlos BaezDec 23

New result: you can build a universal computer using a single billiard ball on a carefully crafted table!

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.

This result is not surprising to me - it would be much more surprising if you *couldn't* make a universal computer this way. Universal computation seems to be a very prevalent feature of sufficiently complex systems. But still it's very nice.

• Eva Miranda and Isaac Ramos, Classical billiards can compute, https://arxiv.org/abs/2512.19156.

Show threadGreg EganDec 23
@johncarlosbaez This is very nice, but I hope it won’t end up attracting the awful kind of pop-sci coverage that makes it sound like the Halting Problem throws some shocking new spanner into the works of classical physics ... as if it had somehow been the case, before Turing and Gödel, that physicists had expected to be able to predict the behaviour of arbitrary systems at arbitrary future times with magical short-cuts that did not require them to calculate arbitrary numbers of intermediate states.
Show threadRobJLowDec 23
@gregeganSF @johncarlosbaez Back when I had a web page, I had a list of pet peeves. High on that list was people making nonsense claims in maths or physics based on misunderstandings of Goedel's theorems.
Show threadJohn Carlos BaezDec 23

@RobJLow @gregeganSF - the risk of crazy pop-sci misinterpretations of this result is why I tried to clarify the dangerously ambiguous phrase "undecidable trajectories" in Miranda's post here:

https://bsky.app/profile/evamirandag.bsky.social/post/3maej2irfqc22

We can't stop the flood of nonsense, but at least we can put the truth out there as best we can, and the truth makes more sense.

Eva Miranda (@evamirandag.bsky.social)

Classical billiards can compute. 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. 🎱🧠 @upc.edu @ricardsole.bsky.social

Bluesky Social
Show threadEva MirandaDec 29
@johncarlosbaez @RobJLow @gregeganSF When a Turing machine is associated to a dynamical system, the notion of Turing completeness means that a trajectory enters an open set is equivalent to the Turing machine halting. So undecidable trajectory comes associated with this notion as the halting is undecidable (Turing). For TKFT models like the ones in these billiards construction Turing completeness comes as a bonus of the TKFT construction in :https://arxiv.org/abs/2503.16100
Topological Kleene Field Theories as a model of computation

In this article, we establish the foundations of a computational field theory, which we term Topological Kleene Field Theory (TKFT), inspired by Stephen Kleene's seminal work on partial recursive functions and drawing parallels with Topological Field Theory. Our central result shows that any computable function can be simulated by the flow on a smooth bordism of a vector field with good local properties, setting an alternative model of computation to Turing machines. We thus establish that a computable function can be fully realized within a single go of a dynamical system, differing from previous works where computation is encoded as an iterative process. The output of the computable function emerges directly, laying the groundwork for potential applications that accelerate the physical realization of computation.

arXiv.org
Show threadEva MirandaDec 29
@johncarlosbaez @RobJLow @gregeganSF such notion of undecidable trajectories also appear in our former work concerning fluids as we prove Euler and Navier-Stokes can be Turing complete.....
Show threadEva MirandaDec 29
@johncarlosbaez @RobJLow @gregeganSF https://www.pnas.org/doi/10.1073/pnas.2026818118
Show threadJohn Carlos BaezDec 29

@evamiranda - thanks for joining the conversation and clarifying! We've got a tough crowd here. 😉

The fluid dynamics example is more impressive to me than the billiard ball because I'm less able to imagine how I'd achieve chosen behavior using fluid flow!

@RobJLow @gregeganSF

Show threadEva MirandaDec 29
@johncarlosbaez @RobJLow @gregeganSF Thanks. The fluid flow hides the following key idea: certain stationary solutions of the Euler or Navier–Stokes equations can be interpreted as Reeb vector fields in contact or cosymplectic geometry. Turing completeness is then achieved by promoting Moore’s two-dimensional construction to three dimensions, by exhibiting a Reeb vector field whose Poincaré section recovers the original Moore 2D dynamics. Moore construction uses mappings of the square cantor set of certain type (called generalized shifts).
Show threadEva MirandaDec 29
@johncarlosbaez @RobJLow @gregeganSF At the end of the day, the Euler equations arise as a continuum limit of the Boltzmann principle, passing from discrete to continuous descriptions. Thus, even though the methods of proof are different, the underlying frameworks are consistent and fit together naturally.
Show threadJohn Carlos Baez

By the way, @evamiranda, you probably know this, but Hilbert posed the problem of rigorously deriving equations of fluid flow from the classical mechanics of elastic hard spheres. This paper claimed to solve that problem:

• Yu Deng, Zaher Hani, and Xiao Ma, "Hilbert's sixth problem: derivation of fluid equations via Boltzmann's kinetic theory" (March 3, 2025): https://arxiv.org/abs/2503.01800

They claimed to derive the Navier-Stokes-Fourier and compressible Euler equations starting from hard sphere particle systems undergoing elastic collisions, going through the Boltzmann equation as an intermediate step.

But this paper raised plausible objections:

• Shan Gao, "Comment on 'Hilbert's Sixth Problem: Derivation of Fluid Equations via Boltzmann's Kinetic Theory' by Deng, Hani, and Ma" (April 7, 2025): https://arxiv.org/abs/2504.06297

Gao's main objection is that the Boltzmann-Grad limit forces the fraction of volume occupied by spheres to approach zero, so the system becomes an infinitely dilute gas throughout the derivation. The subsequent hydrodynamic limit increases collision frequency, but within this fundamentally dilute gas framework: it never actually describes a dense fluid. He argued that this is a "rescaled gas model" rather than a genuine derivation of fluid dynamics. Furthermore, the molecular chaos assumption underlying Boltzmann's equation would break down in any true fluid-density regime.

Hilbert's sixth problem: derivation of fluid equations via Boltzmann's kinetic theory

In this paper, we rigorously derive the fundamental PDEs of fluid mechanics, such as the compressible Euler and incompressible Navier-Stokes-Fourier equations, starting from the hard sphere particle systems undergoing elastic collisions. This resolves Hilbert's sixth problem, as it pertains to the program of deriving the fluid equations from Newton's laws by way of Boltzmann's kinetic theory. The proof relies on the derivation of Boltzmann's equation on 2D and 3D tori, which is an extension of our previous work (arXiv:2408.07818).

arXiv.org
Dec 29 at 9:53pmWeb
Show threadEva MirandaDec 30
@johncarlosbaez I knew about the first paper I will read both.