Undecidable fluid particle paths and 3D fluid computers

INTRODUCTION

In the book The Emperor’s new mind [10] Sir Roger Penrose returns to the artificial intelligence debate to convince us that creativity cannot be presented as the output of a “mind” representable as a Turing machine. This idea, which is platonic in nature and highly philosophical, evolves into more tangible questions such as: What kind of physics might be non-computational? The ideas of the book are a source of inspiration and can be taken to several landscapes and levels of complexity: Is hydrodynamics capable of performing computations? (Moore [9]). Given the Hamiltonian of a quantum many-body system, is there an algorithm to check if it has a spectral gap? (this is known as the spectral gap problem, recently proved to be undecidable [5]). And last but not least, can a mechanical system (including a fluid flow) simulate a universal Turing machine (universality)? (Tao [15, 16, 17]).This last question has been analyzed in relation to the conjecture of the regularity of the Navier-Stokes equations [14], which is one of the unsolved problems in the Clay’s millennium list. In [18] Tao speculates on a connection between a potential blow-up of the Navier-Stokes equations and Turing completeness and fluid computation. It is interesting to mention that another of the one million dollars problem on the same list whose resolution is stillpending is the P versus NP problem, which concerns the complexity of systems. Grosso modo, the question is if any problem whose solution can be verified by an algorithm polynomial in time (“of type NP”) can also be solved by another algorithm polynomial in time (“of typeP”). The delicate distinction between verification and solution has opened up an intricate scenery combining research in theoretical computer science, physics and mathematics. Although there is no apparent relation between these two celebrated problems, understanding a fluid flow as a Turing machine may shed some light on their connection. On the other hand, undecidability of systems is everywhere and also on the invisible fine line between geometry and physics: As proven by Freedman [7] non-abelian topological quantum field theories exhibit the mathematical features (combinatorics) necessary to support an NP-hard model. This relates topological quantum field theory and the Jones polynomial (as described by Witten [19]) to the P6=NPproblem. Other undecidable problems on the crossroads of geometry and physics are the stability of ann-body system [8], the problem of finding an Einsteinmetric for a fixed 4-fold as observed by Wolfram [20], ray tracing problems in 3D optical systems [12], or neuralnetworks [13]. Fundamental questions at the heart of low dimensional geometry and topology such as verifying theequivalence of two finitely specified 4-manifolds [20] or the problem of computing the genus of a knot [1] have also been proven to be undecidable and NP-hard problems, respectively. In [4] we addressed the appearance of undecidable phenomena in fluid dynamics proving the existence of stationary solutions of the Euler equations on a Riemannian 3-dimensional sphere that can simulate any Turing machine (i.e., they are Turing complete). These solutions describe the dynamics of an inviscid and incompressible fluid inequilibrium. The type of flows that we consider are Beltrami fields, a particularly relevant class of steady Euler flows. Our novel strategy fusions the computational power of symbolic dynamics with techniques from contact topologyand its connection with hydrodynamics unveiled by Sullivan, Etnyre and Ghrist more than two decades ago.

To read the full article, download it below.

CONCLUSIONS

Undecidability and chaos.

Because of the undecidability of the halting problem for Turing machines, an important property of a Turing complete dynamical system is the existence of trajectories which exhibit undecidable long-term behavior. Specifically, it is undecidable to determine if the trajectory through an explicit point will intersect an explicit open set of the space. One of the main consequences of the result is that it allows us to prove that certain phenomena of hydrodynamics are undecidable. That is, there is no algorithm to ensure that a fluid particle will pass through a certain region of space in finite time (in metaphoric terms: if we send a message inside a bottle, we cannot guarantee that it will reach its recipient). This inability to predict, which is different from that established by chaos theory, can be understood as a new manifestation of the turbulent behaviour of fluids. In chaos theory, unpredictability is associated with the extreme sensitivity of the system to the initial conditions - the flutter of a butterfly can generate a tornado - in this case: we prove that there can be no algorithm that solves the problem, it is not a limitation of our knowledge, but of the mathematical logic itself.

Theoretical fluid computers and the Navier Stokes problem.

Tao launched a programme in 2016 based on the Turing completeness of the Euler equations to address the blow up problem for the Navier-Stokes equations included in the Clay Foundation’s list of Millennium Problems. Tao’s proposal is, at the moment, speculative. The idea of Tao is to use a Theoretical fluid computer to force the fluid to accumulate more and more energy in smaller regions, until a singularity is formed, that is, a point at which the energy becomes infinite. However, at the moment it is widely open how to do this for the Euler or Navier-Stokes equations.