Computability and Undecidability for Euler Fluids

AUTHOR/EDITOR/ART : R. Ghrist :

This is a review of recent work by R. Cardona, E. Miranda, D. Peralta-Salas, and F. Presas, as per the following works:

R. Cardona, E. Miranda, D. Peralta-Salas, Looking at Euler flows through a contact mirror: Universality and undecidability (2021) https://arxiv.org/abs/2107.09471

R. Cardona, E. Miranda, D. Peralta-Salas, Computability and Beltrami fields in Euclidean space (2021) https://arxiv.org/abs/2111.03559

R. Cardona, E. Miranda, D. Peralta-Salas, F. Presas. Constructing Turing complete Euler flows in dimension 3. Proc. Natl. Acad. Sci. 118 (2021) e2026818118.

R. Cardona, E. Miranda, D. Peralta-Salas, F. Presas. Universality of Euler flows and flexibility of Reeb embeddings (2019) https://arxiv.org/abs/1911.01963

The eponymous Turing machine is a classic model for computation: that the halting problem for general input-program pairs is undecidable is a cornerstone of computability theory. Moore, Penrose, Tao, and others have raised the question of to what degree physical system dynamics performs computations or can simulate Turing machines. One says that a dynamical system is Turing complete if it can simulate any Turing machine. So, in the context of a vector field $X$ on a manifold $M$, Turing completeness of $X$ means that for any Turing machine, input tape, and finite string of symbols in the machine’s alphabet, there exists an explicitly constructible point $p\in M$ and open set $U\subset M$ such that the flowline of $X$ starting at $p$ intersects $U$ if and only if the Turing machine halts with the corresponding output tape. 

Tao in particular has considered computability questions for inviscid fluids [10,11]. An (incompressible) inviscid fluid is a time-dependent vector field $X(x,t)$ on a Riemannian manifold $(M,g)$ satisfying the Euler equations:

\[ \frac{\partial X}{\partial t} + \nabla_XX = -\nabla p \quad ; \quad \nabla\cdot X = 0 . \]

The middle term is the covariant derivative of the field along itself; the right side is the gradient of some scalar field (related to the fluid’s pressure). A steady inviscid fluid is a solution to the Euler equations which is time-independent.

Recent results of Cardona, Miranda, and Peralta-Salas answer several fundamental questions about computability and Turing-completeness of fluid flows using the perspectives and techniques of contact topology.

Recall that a contact form on a $2n+1$-dimensional manifold is a 1-form $\alpha$ satisfying $\alpha\wedge(d\alpha)^n>0$. These odd-dimensional analogues of symplectic 2-forms are the foundation of contact topology, a rich and engaging subject [7]. The Reeb field associated to a contact form is the (nonvanishing) vector field $X$ satisfying $d\alpha(X,\cdot)=0$ and $\alpha(X)=1$ — it is the vector field dual to the 1-form.

It has long been known that the dynamics of the Reeb field implicates and is impacted by the topology of the contact structure: this is the foundation of so many deep results in contact topology, from the Weinstein Conjecture to Symplectic Field Theory and more.

What ties this subject to fluids is the notion of a Beltrami field. A vector field on a Riemannian 3-manifold is called Beltrami if it is parallel to its curl [1]; a similar definition using differential forms works for higher odd dimensions. Beltrami fields are automatically steady Euler fields – the well-known ABC fields are a classic example of Beltrami fields on the Euclidean 3-torus [1]. 

A result of [6] yields a “mirror” that reflects Beltrami fields in fluids and Reeb fields in contact topology: Reeb fields or nonzero rescalings are realizable as Beltrami fields for some Riemannian structure, and nonzero Beltrami fields or nonzero rescalings are realizable as Reeb fields for some contact form.  

The authors of [2,3,4] use a combination of tools to generate a family of beautiful results. The generalized shifts of Moore [8,9] and the construction of bespoke Cantor sets are a direct line to Turing completeness for dynamics. The use of contact topology permits working with homotopy arguments and an h-principle to forge customized Reeb fields which reflect into Eulerian fluids. The culmination of these methods is a set of theorems, of which the following is an exemplar:

Theorem [4]: There exists a steady Euler flow on a Riemannian 3-sphere that is Turing complete. The Riemannian geometry of this 3-sphere can be assumed to be the round metric in the complement of an embedded solid torus.

Additional results [3] include the existence of steady Euler flows on a Riemannian 3-sphere such that, for a constructible set of points on the sphere, the determination of whether these points lie on periodic orbits is undecidable: similar results about bounding the number of periodic orbits as well as determining density or measure of the periodic orbit set are likewise undecidable. Results for higher-dimensional manifolds are also derived [5].

A very exciting breaking development (November 2021) is the construction of a Turing-complete field not on a compact Riemannian 3-manifold of some hard-to-describe Riemannian geometry, but rather in the standard Euclidean 3-space.

Theorem [2]: There exists a Beltrami field on Euclidean $\mathbb{R}^3$ that can simulate a Turing machine – that is, the field is Turing complete.

The computations in this Euclidean example do not occur within a compact set, unlike those of the fields on non-Euclidean $\mathbb{R}^3$ examples from [4].

Such issues of decidability in fluids are a fascinating aspect of the continued search for a proof of existence or nonexistence of finite-time blow-ups in the Euler or Navier-Stokes equations.

BIBLIOGRAPHY

[1] V. I. Arnold, B. Khesin, Topological Methods in Hydrodynamics. Springer, New York (1999).

[2] R. Cardona, E. Miranda, D. Peralta-Salas, Computability and Beltrami fields in Euclidean space (2021) https://arxiv.org/abs/2111.03559

[3] R. Cardona, E. Miranda, D. Peralta-Salas, Looking at Euler flows through a contact mirror: Universality and undecidability (2021) https://arxiv.org/abs/2107.09471

[4] R. Cardona, E. Miranda, D. Peralta-Salas, F. Presas. Constructing Turing complete Euler flows in dimension 3. Proc. Natl. Acad. Sci. 118 (2021) e2026818118.

[5] R. Cardona, E. Miranda, D. Peralta-Salas, F. Presas. Universality of Euler flows and flexibility of Reeb embeddings (2019) https://arxiv.org/abs/1911.01963

[6] J. Etnyre, R. Ghrist, Contact topology and hydrodynamics I. Beltrami fields and the Seifert conjecture. Nonlinearity 13 441–458 (2000).

[7] H. Geiges, Introduction to contact topology, Cambridge Univ. Press, Cambridge, 2008.

[8] C. Moore. Unpredictability and undecidability in dynamical systems. Phys. Rev. Lett. 64 (1990) 2354–2357.

[9] C. Moore. Generalized shifts: unpredictability and undecidability in dynamical systems. Nonlinearity 4 (1991) 199–230.

[10] T. Tao. On the universality of the incompressible Euler equation on compact manifolds. Discrete Cont. Dyn. Sys. A 38 (2018) 1553–1565.

[11] T. Tao. On the universality of the incompressible Euler equation on compact manifolds, II. Nonrigidity of Euler flows. Pure Appl. Funct. Anal. 5 (2020) 1425–1443.

.

Share this post

Share on facebook
Share on google
Share on twitter
Share on linkedin
Share on pinterest
Share on print
Share on email