Mastodawn

Badibulgator Dec 24

John Carlos Baez

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.

Pino Carafa Dec 23

@johncarlosbaez Ah yes that reminds me of how I solved the Riemann conjecture in the local snooker hall...

John Carlos Baez Dec 23

@rozeboosje - I was trying to prove it first using an exhaustive proof search, but I got snookered.

Weekend Editor Dec 23

@johncarlosbaez @rozeboosje

I once tried exhaustive proof search, but I just got exhausted.

Greg Egan Dec 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.

@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.

John Carlos Baez Dec 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

@johncarlosbaez @gregeganSF There must be some nasty subtleties lying around: for a start, there are uncountably many different initial states, but only countably many Turing machines, so in one sense it's entirely unsurprising that TMs can't capture the behaviour of billiards. (I guess the trick is to show that it can't capture the behaviour in an interesting way.)

John Carlos Baez Dec 23

@RobJLow @gregeganSF - Just so everyone gets it: a Turing machine can't perfectly simulate a billiard ball because the billiard ball has uncountably many states while any Turing machine has just countably many states. This paper claims to show that a billiard ball can simulate a universal Turing machine.

To do this, they take the state space of the billiard ball and choose countably many disjoint open intervals embedded in the boundary of the billiard table to describe initial states of the Turing machine. Then the machine runs when the ball fires off at right angles to the boundary and bounces around. They say the machine "halts" if the billiard ball's trajectory is periodic.

Now that I'm looking hard at the paper, I'm getting some questions which I'm not able to instantly answer... hence my word "claims" above.

But anyway, once you get a system acting like a universal Turing machine, we know the question of whether it "halts" for an arbitrary initial state is unsolvable by any Turing machine. That's the result this paper uses to prove

Corollary 2. There exists a two-dimensional billiard table for which deciding whether a given trajectory is periodic is algorithmically undecidable.

Daniel Lakeland Dec 23

@johncarlosbaez
Intuitively, even ignoring the periodicity issue. one might want to ask the question does the machine reach a given state (we could label this single state the halting state for example). to answer that question we may need to watch the balls trajectory forever to say that no, it doesn't hit that piece of the table boundary. just like we might need to simulate a Turing machine forever to say no it doesn't halt.
@RobJLow @gregeganSF

Refurio Anachro Dec 23

Such a shame that photons aren't point particles. That would make for a fascinating lamp! Orb of wisdom or something.

@johncarlosbaez @RobJLow @gregeganSF

@johncarlosbaez @RobJLow @gregeganSF

@johncarlosbaez thanks for the TLDR of their mapping, now I don't need to filter the paper for that info.

@gregeganSF The fun thing is that in this system one can calculate the system at arbitrary future times (you're also right that there are no shortcuts, but that is inevitably encoded in the word "computation"). [Edit: and even having an oracle with that shortcut power would not touch the problem of undecidability.]

So this perspective goes besides the point of undecidability, and this is i.m.o. the crux about all the misunderstandings. It is not "undecidable" to calculate the trajectory (and its less clear what that even is supposed to mean). Its the decission problem, whether the trajectory has or doesn't have a certain property, which is undecidable.
And in this phrasing the undecidability is suddenly not-surprising-at-all even to the lay person: If the property can take arbitrarily long to realize (like an arbitrarily long periodic path), how should we ever decide that we have waited sufficiently arbitrarily long to tell...

In that spirit, I find the sentence about "undecidable trajectories" in the papers abstract borderline misleading (and yet I totally understand that its sexy to write). And I find the debate about undecidability often covered in too much miraculous dust — the abstract would be much more transparent yet also way more boring if it just stated that they show that periodic-nes of trajectories is undecidable.

John Carlos Baez Dec 23

@papalex @RobJLow @gregeganSF - yes, "undecidable trajectories" doesn't make sense (you can't decide a trajectory, you can decide the answer to a question), and the abstract would be much more helpful if it simply stated their theorem. "Sexiness" often results from concealing the most important bits - in writing as in clothing.

Eva Miranda Dec 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

Eva Miranda Dec 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.....

Eva Miranda Dec 29

@johncarlosbaez @RobJLow @gregeganSF https://www.pnas.org/doi/10.1073/pnas.2026818118

John Carlos Baez Dec 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

Eva Miranda Dec 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).

Eva Miranda Dec 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.

John Carlos Baez Dec 29

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

Eva Miranda Dec 30

@johncarlosbaez I knew about the first paper I will read both.

i_dont_like_AI a_programmer Jan 21

@RobJLow @gregeganSF @johncarlosbaez

Awesome. Myself, I have almost never met anybody who has any serious opinion on Goedel's theorems at all (okay, 3 people). For me be socially surprising, if I suddenly ran into lots of people misinterpreting Goedel. Far better to misinterpret Goedel than to have never heard about Goedel. There are plenty of discussions eg in the Royal Society journals in the decades after he wrote his articles showing a multitude of honorable (mis)understandings.

Ben Hourahine Dec 23

@gregeganSF @johncarlosbaez on the other hand, it strongly suggests Philip Anderson's "more is different" position is correct (infinite size Ising-like cellular automata with a halting problem being the best previous example).

Elias Mårtenson Dec 23

@johncarlosbaez I started reading it, and although I'm certainly not qualified to critique it, I think I understand the gist of it.

I found this to be absolutely fascinating. I mean, sure, when you think about the paths the ball can take, you kinda get it, but it's still interesting.

My question is, the proof does not rely on chaotic systems, but if you implement a turing machine that simulates a chaotic system, does that make the entire system chaotic?

John Carlos Baez Dec 23

@loke - since a Turing machine has a discrete set of states, it's impossible for it to exactly simulate a chaotic system, since those have a continuous *space* of states. So, the answer to your question depends on how we deal with this issue.

Phil Gibbs Dec 23

@johncarlosbaez I find it surprising that such a paper can be written without even a passing mention of Feynman's very well known billiard ball model of reversible computing from the Feynman Lectures on Computation.

John Carlos Baez Dec 23

@philg - did they really not mention that, while listing so much previous work on billiard ball physics?

Phil Gibbs Dec 24

@johncarlosbaez I looked a little deeper and found that Feynman was just popularising the work of Edward Fredkin and Tommaso Toffoli who are cited in this paper even though Feynman isn't. Fredkin and Toffoli showed that classical billiard ball dynamics as a basis for computation is Turing complete. This already seems to cover the title of the new paper, which leaves me wondering what their new result is.

Perhaps there method is different and more robust? The abstract does not clarify. I am sure there must be something new and worthwhile there, but I wish they would state what it is. Looking a little further again, they seem to be looking at a system with just one billiard ball and a complicated table shape, which is very different from the prior system of colliding multiple billiard balls.

Eva Miranda Dec 29

@philg @johncarlosbaez Just one ball in this article, several balls in the work of Fredkin and Toffoli

Eva Miranda Dec 29

@philg @johncarlosbaez we are citing Feynman in the new version of the article, however referring to his approach to computation rather than the billiard ball section that follows the work of Fredkin and Toffoli

Phil Gibbs Dec 30

@evamiranda @johncarlosbaez Eva, it is a great piece of work. Glad to hear you are building on it further

Eva Miranda Dec 30

@philg @johncarlosbaez Thank you, Phil!

Bartosz Milewski Dec 24

@johncarlosbaez
I can imagine Stephen Wolfram's dilemma: Is the universe a cellular automaton? Or was I wrong all along, and it's a billiard ball?

Tony Vladusich Jan 5

@johncarlosbaez

That’s a pretty ballsy paper!

John Carlos Baez Jan 5

@TonyVladusich -

https://mathstodon.xyz/@evamiranda/115844806955127261