Search

Can every physical system simulate any Turing machine? This is a classical problem that is intimately connected with the undecidability of certain physical phenomena. Concerning fluid flows, Moore [C. Moore, Nonlinearity 4, 199 (1991)] asked if hydrodynamics is capable of performing computations. More recently, Tao launched a program based on the Turing completeness of the Euler equations to address the blow-up problem in the Navier¿Stokes equations. In this direction, the undecidability of some physical systems has been studied in recent years, from the quantum gap problem to quantum-field theories. To the best of our knowledge, the existence of undecidable particle paths of three-dimensional fluid flows has remained an elusive open problem since Moore¿s works in the early 1990s. In this article, we construct a Turing complete stationary Euler flow on a Riemannian S3 and speculate on its implications concerning Tao¿s approach to the blow-up problem in the Navier¿Stokes equations., Robert Cardona was supported by the Spanish Ministry of Economy and Competitiveness, through the María de Maeztu Program for Units of Excellence in R&D (MDM-2014-0445) via an FPI grant. R.C. and E.M. are partially supported by Grants MTM2015-69135-P/FEDER, the Spanish Ministry of Science and Innovation PID2019-103849GB-I00/AEI/10.13039/501100011033, and Agència de Gestió d’Ajuts Universitaris i de Recerca Grant 2017SGR932. E.M. is supported by the Catalan Institution for Research and Advanced Studies via an ICREA Academia Prize 2016. D.P.-S. is supported by MICINN Grant MTM PID2019-106715GB-C21 and MCIU Grant Europa Excelencia EUR2019-103821. F.P. is supported by MICINN/FEDER Grants MTM2016-79400-P and PID2019-108936GB-C21. This work was partially supported by ICMAT–Severo Ochoa Grant CEX2019-000904-S.

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., 13 pages, 1 figure

[ES]En este trabajo nos centraremos en los autómatas celulares (ACs) reversibles. Estos ACs se ca-racterizan por el hecho de que cada configuración tiene un único predecesor. Por tanto, dada cualquier configuración, podemos determinar su evolución hacia atrás en el tiempo. Fundamentalmente, los ACs reversibles son muy útiles para modelar sistemas dinámicos que son reversibles en el tiempo, en particular, sistemas que evolucionan de acuerdo con las leyes de la mecánica clásica. En el primer capítulo daremos la definición matemática de AC, estudiaremos la topología del espacio de configuraciones y probaremos el teorema de Curtis-Hedlund-Lyndon que caracteriza a los ACs. En el segundo capítulo veremos la definición de AC reversible y estudiaremos varias propiedades relacionadas con la inyectividad y la epiyetividad para simplificar la condición de reversibilidad. En el tercer capítulo veremos el teorema más conocido sobre los ACs, el teorema del Jardín del Edén, relacionado con ACs que tiene configuraciones sin predecesores. Dedicaremos el cuarto capítulo a un estudio más detallado de los ACs unidimensionales. Primero veremos que es posible simplificar la reversibilidad de un AC a su inyectividad sobre configuraciones periódicas y posteriormente usaremos gráficos de Bruijn para estudiar a los ACs. En el quinto capítulo trataremos los ACs particionados, los cuales resultan un método simple de construir ACs reversibles, y mostraremos que los ACs reversibles unidimensionales son Turing completos. En el sexto y último capítulo discutiremos las posibles aplicaciones de los ACs reversibles., [EN]In this work we will focus on reversible cellular automata (RCA). RCA are characterized by the fact that every configuration has a single predecessor. Therefore, given any configuration, we can determine its evolution backwards in time. Crucially, RCA are very useful for modeling dynamical systems which are reversible in time, in particular, systems that evolve according to the laws of classical mechanics. In the first chapter we will give the mathematical definition of CA, we will study the topology of the configuration space and we will prove the Curtis-Hedlund-Lyndon theorem that characterizes CA. In the second chapter we will see the defini-tion of RCA and we will study various properties relating to injectivity and surjectivity in order to simplify the reversibility condition. In the third chapter we will see the best known theorem about CA, the Garden of Eden theorem, relating to CA which have configurations without pre-decessors. We will dedicate the fourth chapter to a more detailed study of one-dimensional CA. First we will see that it is possible to simplify the reversibility of CA to their injectivity over periodic configurations and then we will use de Bruijn graphs to study these CA. In the fifth chapter we will discuss partitioned CA, which are a simple method of constructing RCA, and we will show that one-dimensional RCA are Turing complete. In the sixth and final chapter we will discuss possible applications of RCA.