- The results of the research show that some phenomena in hydrodynamics are undecidable problems: it is impossible to construct an algorithm always leading to an answer in finite time.
- The results obtained represent a new manifestation of the turbulent nature of fluid movement.
- Knowledge from diverse areas of mathematics had to be combined to successfully reach this milestone, involving researchers of ICMAT-CSIC, UPC- BGSMath and UPC-CRM Observatoire de Paris.
In the year 2014, the Australian Fields Medal awardee Terence Tao, notorious for his panoramic, if not comprehensive, view of current mathematics, proposed a new approach towards the famous problem of the Navier-Stokes equations, which describe the movement of fluids.
Motivated by the approach proposed by Tao, a team of researchers of ICMAT-CSIC, UPC–BGSMath and UPC-CRM Observatoire de Paris managed for the first time to obtain mathematical solutions of a fluid capable of simulating any Turing machine. The result was published at the journal Proceedings of the National Academy of Sciences (PNAS).
A Universal Turing water machine
Turing Machines were invented by Alan Turing in the year 1936. A Turing machine is an abstract mathematical construction capable of simulating any algorithm. It takes as input a sequence of binary data (0 or 1 values) and, after a given number of steps, returns another binary string of data as a result. Turing machines have been used, for instance, to show in the past the existence of inherent limitations of mechanical computation.
In this particular development, the fluid studied by the researchers could be considered as a water Universal Turing Machine: it takes as entry data a point in space, processes it -following the trajectory of the fluid through that point- and provides as an output result the next region towards which the fluid has moved. The result is an incompressible 3D fluid without viscosity (Navier-Stokes equations do consider viscosity). This development represents the first time in which a Universal Turing water machine has been successfully designed.
One of the main consequences of the obtained results is that it allows to prove that certain hydrodynamic phenomena are undecidable, meaning that these phenomena cannot be proven/predicted by any algorithm with guarantee of obtaining a result in finite time. A related example is that, if we throw a message in a bottle into the sea, we cannot assure that it will ever reach any specific destination given a finite amount of time. Something alike happened to a large batch of 29000 plastic ducks that fell from a cargo ship during a storm and were lost in the ocean in 1992: nobody could predict where they would appear.
No algorithm exists that can ensure that a certain particle belonging to a fluid will traverse a particular region of space in a finite amount of time. “This impossibility for prediction, which is different to the one established by chaos theory, is a new manifestation of the turbulent behaviour of liquids”, say the researchers.
“In chaos theory, unpredictability is associated to an extreme sensitivity of the system with regard to starting conditions -a butterfly moving its wings may ultimately be able to originate a tornado- , something that in this case goes even beyond: it is proven that there cannot be an algorithm able to solve the problem, and this is something which is not due to a limitation of our knowledge, but to the mathematical logic itself”, highlight Miranda and Peralta-Salas. This shows the complexity of the behaviour of fluids, which shows itself in numerous fields: from the prediction of atmospheric time to the dynamics in streams and waterfalls, among others.
Regarding its relation with the Navier-Stokes problem, including the list of the seven Millenium Problems of the Clay Foundation, researchers are cautious: “The proposal of Tao is, for now, hypothetical”, they assure. His idea is to use a water computer to force a fluid to accumulate more and more energy in increasingly small regions, until a singularity is formed; that is, a point in which energy becomes infinite. The existence or not of singularities in equations is, precisely, the problem of Navier-Stokes. Nonetheless, “for now it is not known how to do this for Euler or Navier-Stokes equations”, say the scientists, who discussed their results with Tao himself.
This research started after Eva Miranda, ICREA Academy Professor of the Polytechnic University of Catalonia (UPC)-IMTech, member of the Centre de Recerca Matemàtica (CRM) and the Observatoire de Paris (France), encountered the original publication at one of the related articles at the blog of Prof. Tao, which readily captured her attention. At the time, Miranda was finishing a work with Daniel Peralta-Salas (ICMAT-CSIC) and Robert Cardona (BGSMath-CSIC) about fluids in spaces with boundaries. The team was later expanded with Francisco Presas (ICMAT-CSIC) managing for the first time to construct solutions for a fluid capable of simulating any Turing machine.
The water machine of Cardona, Miranda, Peralta-Salas and Presas -the first one to ever exist-, is guided by the equations of Euler, but its solutions do not have any singularities. For its design, tools from the fields of geometry, topology and dynamical systems developed in the last 30 years have been key. In particular, simplectic and contact geometry, together with fluid dynamics, computation science theory and mathematical logic are combined. “It has cost us more than a year to understand how to connect the various logical threads involved in the demonstration”, conclude the scientists, highlighting the high complexity of this feat.
Image credits:
Model of a Turing Machine was downloaded from Wikipedia and licensed via a Creative Commons Attribution 3.0 Unported (CC BY 3.0) license.
Turbulent waters picture was downloaded from Flickr and licensed via a Creative Commons Attribution-NonCommercial-NoDerivs 2.0 Generic (CC BY-NC-ND 2.0) license.
Picture of the involved researchers was kindly provided by ICMAT.