UPC researchers obtain for the first time solutions for a fluid capable of simulating any Turing machine
Researchers from the UPC’s Geometry of Manifolds and Applications (GEOMVAP) research group and the CSIC’s Institute of Mathematical Sciences have managed, for the first time, to construct solutions for a fluid capable of simulating any Turing machine. The result of the study was published in the journal 'Proceedings of the National Academy of Sciences (PNAS)'.
Jul 20, 2021
Seven years ago, Fields Medalist Terence Tao, famous for his broad view of current mathematical research, proposed a new approach to solve the well-known problem of the Navier-Stokes equations, which describe the motion of fluids. The project, published on Tao’s blog, caught the attention of Eva Miranda, an ICREA Acadèmia professor and a researcher from the Geometry of Manifolds and Applications (GEOMVAP) research group of the Universitat Politècnica de Catalunya · BarcelonaTech (UPC), who at the time was finishing a project on fluids in bounding areas with researchers Daniel Peralta-Salas, from the Institute of Mathematical Sciences of the Spanish National Research Council (ICMAT-CSIC), and Robert Cardona, a researcher from the UPC’s GEOMVAP. Now, the researchers, joined by Francisco Presas (ICMAT-CSIC) and motivated by Tao’s approach, have managed for the first time to construct solutions for a fluid capable of simulating any Turing machine. The study was published in the journal Proceedings of the National Academy of Sciences (PNAS).
A Turing machine is an abstract construction that is capable of simulating any algorithm. As input data, it receives a sequence of zeros and ones and, after a number of steps, it gives a result that is also binary. The fluid studied by the researchers can be considered a water machine: it takes a point in space as input, it processes it by following the trajectory of the fluid through that point and it offers as a result the next region where the fluid has travelled to. The result is an incompressible and non-viscous fluid - the Navier-Stokes equations do consider viscosity - in dimension three. This is the first successful water machine ever designed.
The result mainly allows the researchers to prove that certain hydrodynamic phenomena are undecidable. For example, if we send a message in a bottle, there is no guarantee that it will reach its recipient. A similar situation happened with the 29,000 rubber ducks that fell from a cargo ship in a storm and disappeared in the ocean in 1992: no one could predict where they would end up. In other words, there is no algorithm to ensure whether a fluid particle will pass through a certain region of space in finite time. “This inability to predict, which is different from that established by chaos theory, is a new manifestation of the turbulent behaviour of fluids”, explain the researchers.
“In chaos theory, unpredictability is associated with the extreme sensitivity of the system to initial conditions - a butterfly flapping its wings can cause a hurricane. In this case it goes further: we proved that there can be no algorithm that solves the problem, it is not a limitation of our knowledge but of the mathematical logic itself”, as Miranda and Peralta-Salas highlight. This shows the complex behaviour of fluids, which affects several areas, such as weather forecasting and the dynamics of flows and waterfalls.
As for its relationship with the Navier-Stokes problem, which is one of the Millennium Prize Problems stated by the Clay Mathematics Institute, the researchers are cautious. “Tao’s proposal is, for now, hypothetical”, they explain. His idea is to use a water computer to force the fluid to accumulate more and more energy in smaller and smaller areas, until singularities are formed, that is, a point at which the energy becomes unlimited. The existence or non-existence of singularities in equations is precisely the Navier-Stokes problem. However, “at the moment no one can do this for the Euler or Navier-Stokes equations”, say the scientists, who have discussed their findings with Tao.
The Cardona, Miranda, Peralta-Salas and Presas water machine - the first to exist - is governed by Euler equations, but their solutions have no singularities. Several geometry, topology and dynamic systems tools developed in the last 30 years have been key to its design. Specifically, it combines symplectic and contact geometry and fluid dynamics with computer science theory and mathematical logic. “It has taken us more than a year to understand how to connect the various cables of the demonstration”, admit the scientists.
A Turing machine is an abstract construction that is capable of simulating any algorithm. As input data, it receives a sequence of zeros and ones and, after a number of steps, it gives a result that is also binary. The fluid studied by the researchers can be considered a water machine: it takes a point in space as input, it processes it by following the trajectory of the fluid through that point and it offers as a result the next region where the fluid has travelled to. The result is an incompressible and non-viscous fluid - the Navier-Stokes equations do consider viscosity - in dimension three. This is the first successful water machine ever designed.
The result mainly allows the researchers to prove that certain hydrodynamic phenomena are undecidable. For example, if we send a message in a bottle, there is no guarantee that it will reach its recipient. A similar situation happened with the 29,000 rubber ducks that fell from a cargo ship in a storm and disappeared in the ocean in 1992: no one could predict where they would end up. In other words, there is no algorithm to ensure whether a fluid particle will pass through a certain region of space in finite time. “This inability to predict, which is different from that established by chaos theory, is a new manifestation of the turbulent behaviour of fluids”, explain the researchers.
“In chaos theory, unpredictability is associated with the extreme sensitivity of the system to initial conditions - a butterfly flapping its wings can cause a hurricane. In this case it goes further: we proved that there can be no algorithm that solves the problem, it is not a limitation of our knowledge but of the mathematical logic itself”, as Miranda and Peralta-Salas highlight. This shows the complex behaviour of fluids, which affects several areas, such as weather forecasting and the dynamics of flows and waterfalls.
As for its relationship with the Navier-Stokes problem, which is one of the Millennium Prize Problems stated by the Clay Mathematics Institute, the researchers are cautious. “Tao’s proposal is, for now, hypothetical”, they explain. His idea is to use a water computer to force the fluid to accumulate more and more energy in smaller and smaller areas, until singularities are formed, that is, a point at which the energy becomes unlimited. The existence or non-existence of singularities in equations is precisely the Navier-Stokes problem. However, “at the moment no one can do this for the Euler or Navier-Stokes equations”, say the scientists, who have discussed their findings with Tao.
The Cardona, Miranda, Peralta-Salas and Presas water machine - the first to exist - is governed by Euler equations, but their solutions have no singularities. Several geometry, topology and dynamic systems tools developed in the last 30 years have been key to its design. Specifically, it combines symplectic and contact geometry and fluid dynamics with computer science theory and mathematical logic. “It has taken us more than a year to understand how to connect the various cables of the demonstration”, admit the scientists.