Turing universality of the incompressible Euler equations and a conjecture of Moore

Abstract

In this article we construct a compact Riemannian manifold of high dimension on which the time dependent Euler equations are Turing complete. More precisely, the halting of any Turing machine with a given input is equivalent to a certain global solution of the Euler equations entering a certain open set in the space of divergence-free vector fields. In particular, this implies the undecidability of whether a solution to the Euler equations with an initial datum will reach a certain open set or not in the space of divergence-free fields. This result goes one step further in Tao's programme to study the blow-up problem for the Euler and Navier-Stokes equations using fluid computers. As a remarkable spin-off, our method of proof allows us to give a counterexample to a conjecture of Moore dating back to 1998 on the non-existence of analytic maps on compact manifolds that are Turing complete.

arXiv comment13 pages, 1 figure

References in corpus (3)

• Constructing Turing complete Euler flows in dimension $3$
• Universality of Euler flows and flexibility of Reeb embeddings
• A Survey on Continuous Time Computations

Cited by in corpus (5)

• Universality of Euler flows and flexibility of Reeb embeddings
• Computability and Beltrami fields in Euclidean space
• Towards a Fluid computer
• Robust non-computability of dynamical systems and computability of robust dynamical systems
• On the algorithmic descriptive complexity of attractors in topological dynamics