Navier-Stokes Undecidability — When Fluid Dynamics Encodes the Halting Problem
A steady fluid can compute forever without the fluid itself changing. In a 2025 arXiv preprint, Søren Dyhr, Ángel González-Prieto, Eva Miranda, and Daniel Peralta-Salas construct stationary Navier-Stokes solutions on certain compact 3-manifolds whose particle paths simulate a universal Turing machine. The undecidable question is not whether the velocity field evolves badly. It is whether one marked particle ever reaches one marked region.
The case
Navier-Stokes usually enters the room as a turbulence problem: velocity changes over time, vortices stretch, viscosity drains energy. The Dyhr-González-Prieto-Miranda-Peralta-Salas result is colder than that. The velocity field is stationary, so the movie frame never changes, but a particle carried through the frame can trace a computation with no general stopping test.
The core equation for incompressible flow is:
∂u/∂t + (u · ∇)u = -∇p + νΔu
∇ · u = 0
Here u is velocity, p is pressure, and ν is viscosity. In the steady case, ∂u/∂t = 0. The construction uses 3-manifolds with nonvanishing harmonic 1-forms, then connects harmonic vector fields to cosymplectic geometry. That geometry gives enough routing structure for particle paths to encode computation.
The sharp line is this: viscosity does not automatically make a fluid mathematically tame.
What is actually undecidable
The halting problem says there is no algorithm that decides, for every program and input, whether that program stops. Fluid undecidability imports that limit into a geometric question.
| Computation object | Fluid object |
|---|---|
| Turing machine | Stationary velocity field |
| Input tape | Initial particle position |
| Halting state | Target region in the manifold |
| Does it halt? | Does the particle enter the region? |
This does not mean every real-world pipe flow hides an undecidable theorem. It means the Navier-Stokes equations, on the right geometric stage, can host dynamics rich enough to inherit the halting problem.
The lineage
Cristopher Moore asked in the 1990s whether hydrodynamic systems could compute. Terence Tao revived the question in his 2016 paper on finite-time blowup for an averaged 3D Navier-Stokes equation, partly as a route into the Clay problem.
In 2021, Cardona, Miranda, Peralta-Salas, and Presas built Turing-complete stationary Euler flows in dimension 3. Euler has no viscosity. The 2025 Navier-Stokes preprint matters because viscosity is the term many people expect to erase fine computational structure. The result says: not on every manifold, and not for every question.
What is contested
The Millennium Prize problem is still untouched. Clay's Navier-Stokes question asks about smooth global solutions in 3D Euclidean space or the 3-torus, with precise energy and smoothness conditions. The 2025 construction lives on certain compact Riemannian 3-manifolds and concerns Lagrangian particle paths, not blowup of the velocity field.
The live question is transfer. Can this computational machinery be moved closer to flat physical domains, finite-energy flows, or the exact Clay setting? If not, the result remains a theorem about the reach of the equations under special geometry, not a forecast about ordinary turbulence.
Why this has to do with other realms
The same pattern appears in quantum physics. Cubitt, Pérez-García, and Wolf proved in 2015 that the spectral gap problem is undecidable for certain quantum many-body Hamiltonians. The shared move is not “physics is mysterious.” It is more exact: build a physical system whose long-range behavior depends on a hidden computation.
That makes this page sit between concept halting problem and concept turbulence. It also points at concept godel incompleteness because the limit is not measurement error. It is a boundary inside formal prediction itself.
An open question
If computation can hide inside a steady viscous flow, which other “settled” physical equations are only settled because nobody has asked the right reachability question yet?
Key Sources
- Dyhr, González-Prieto, Miranda, and Peralta-Salas, “Turing complete Navier-Stokes steady states via cosymplectic geometry” (arXiv:2507.07696, 2025) - the direct Navier-Stokes construction.
- Cardona, Miranda, Peralta-Salas, and Presas, “Constructing Turing complete Euler flows in dimension 3” (PNAS, 2021; arXiv:2012.12828) - the 3D Euler predecessor.
- Cardona, Miranda, and Peralta-Salas, “Turing universality of the incompressible Euler equations and a conjecture of Moore” (arXiv:2104.04356, 2021) - the broader Euler universality result.
- Tao, “Finite time blowup for an averaged three-dimensional Navier-Stokes equation” (JAMS, 2016) - the computation-through-fluid-dynamics program around blowup.
- Cubitt, Pérez-García, and Wolf, “Undecidability of the Spectral Gap” (Nature, 2015; arXiv:1502.04573) - the quantum many-body parallel.
- Charles Fefferman, “Existence and Smoothness of the Navier-Stokes Equation” (Clay Mathematics Institute, 2000) - the official Millennium Prize statement.
Further Reading
- concept navier stokes singularities - the separate blowup question, where velocity regularity rather than particle reachability is the prize.
- concept spontaneous stochasticity - a physical prediction limit caused by noise amplification, not formal undecidability.
- concept cellular automata - the cleanest toy model for seeing how tiny local rules become universal computation.
- Terence Tao, “Why global regularity for Navier-Stokes is hard” (Tao blog, 2007) - a technical map of the Clay problem’s traps.
- Cristopher Moore, “Generalized shifts: unpredictability and undecidability in dynamical systems” (Nonlinearity, 1990) - an early route from dynamical systems to computation.
See Also
- concept halting problem
- concept godel incompleteness
- concept turbulence
- concept navier stokes singularities
- concept spontaneous stochasticity
- concept cellular automata
- concept information theory
- concept temporal asymmetry ai
Abhishek's take
The part that grabs me is not that fluids can be “like computers.” It is that the computation can sit inside a steady object, with no changing machinery on the surface. That is a useful warning for systems work: a dashboard can look static while the state space beneath it is already doing something no rulebook can fully compress.
Tags: #navier-stokes #undecidability #turing-complete #halting-problem #fluid-dynamics #godel #millennium-prize