Chemins indécidables de particules fluides et ordinateurs fluides 3D

INTRODUCTION

Dans son livre The Emperor's new mind1 , Sir Roger Penrose revient sur le débat sur l'intelligence artificielle pour nous convaincre que la créativité ne peut être présentée comme le résultat d'un "esprit" représentable comme une machine de Turing. Cette idée, de nature platonique et hautement philosophique, évolue vers des questions plus tangibles telles que : quelle sorte de physique pourrait être non-computationnelle ?

Les idées de ce livre sont une source d'inspiration et peuvent être amenées à plusieurs paysages et niveaux de complexité : l'hydrodynamique est-elle capable d'effectuer des calculs ?2 .  Étant donné l'hamiltonien d'un système quantique à plusieurs corps, existe-t-il un algorithme permettant de vérifier s'il a un écart spectral ? (On parle alors du problème de l'écart spectral qui s'est récemment avéré indécidable3 .) Enfin, un système mécanique (y compris un écoulement d'un fluide) peut-il simuler une machine de Turing universelle (l'universalité) ?4

Cette dernière question a été analysée en relation avec la conjecture de régularité des équations de Navier-Stokes5 , qui est un des problèmes non résolus de la liste du millénaire de Clay. Dans un article6 , Tao spécule sur l'existence d'un lien entre une explosion potentielle des équations de Navier-Stokes, la complétude de Turing et le calcul des fluides. Il est intéressant de mentionner qu'un autre des problèmes à un million de dollars de la même liste, dont la résolution est toujours en suspens, est le problème P vs. NP, qui concerne la complexité des systèmes. Grosso modo, la question est de savoir si tout problème dont la solution peut être vérifiée par un algorithme en temps polynomial ("de type NP") peut également être résolu par un autre algorithme en temps polynomial ("de type P"). La distinction délicate entre la vérification et la solution a ouvert un paysage complexe de recherche combinant l'informatique théorique, la physique et les mathématiques. Bien qu'il n'y ait pas de relation apparente entre ces deux problèmes célèbres, la compréhension d'un écoulement de fluide comme une machine de Turing peut jeter un certain éclairage sur leur connexion.

D'autre part, l'indécidabilité des systèmes est partout et aussi sur la fine ligne invisible entre la géométrie et la physique : comme l'a prouvé Freedman7 , les théories topologiques non abéliennes des champs quantiques présentent les caractéristiques mathématiques (combinatoires) nécessaires pour soutenir un modèle NP-hard. Ceci relie la théorie des champs quantiques topologiques et le polynôme de Jones (tel que décrit par Witten8 ) au problème P $\ne$ NP. Comme autres problèmes indécidables à la croisée de la géométrie et de la physique, citons la stabilité d'un système à quatre corps9 , le problème de la recherche d'une métrique d'Einstein pour un quadruple fixe tel qu'observé par Wolfram10 , les problèmes de traçage de rayons dans les systèmes optiques 3D11 , ou encore les réseaux neuronaux12 . Des questions fondamentales au cœur de la géométrie et de la topologie de basse dimension, telles que la vérification de l'équivalence de deux quadruplets finiment spécifiés13 ou le problème du calcul du genre d'un nœud14 , se sont également avérées être des problèmes indécidables et NP-durs, respectivement.

Dans un article15 , nous avons abordé l'apparition de phénomènes indécidables en dynamique des fluides en prouvant l'existence de solutions stationnaires des équations d'Euler sur une sphère riemannienne tridimensionnelle qui peuvent simuler n'importe quelle machine de Turing (c'est-à-dire qu'elles sont complètes pour Turing). Ces solutions décrivent la dynamique d'un fluide inviscide et incompressible en équilibre. Le type d'écoulements que nous considérons sont les champs de Beltrami, une classe particulièrement pertinente d'écoulements d'Euler stationnaires. Notre nouvelle stratégie fusionne la puissance de calcul de la dynamique symbolique avec les techniques de la topologie de contact et sa connexion avec l'hydrodynamique dévoilée par Sullivan, Etnyre et Ghrist il y a plus de deux décennies.

Pour lire le texte complet de l'actualité scientifique, téléchargez-le ci-dessous.

• 1R. Penrose. The emperor’s new mind. Concerning computers, minds, and the laws of physics. With a foreword by Martin Gardner. The Clarendon Press, Oxford University Press, New York, 1989. xiv+466 pp. ISBN: 0-19-851973-7
• 2C. Moore. Generalized shifts: unpredictability and undecidability in dynamical systems. Nonlinearity 4 (1991) 199–230.
• 3T. Cubitt, D. Perez-Garcia, M. Wolf. Undecidability of the spectral gap. Nature 528 (2015) 207–211.
• 4T. Tao. On the universality of potential well dynamics. Dyn. PDE 14 (2017) 219-238. / T. Tao. On the universality of the incompressible Euler equation on compact manifolds. Discrete and Continuous Dynamical Systems - A (2018) 38 (3) : 1553-1565. / T. Tao. On the universality of the incompressible Euler equation on compact manifolds, II. Nonrigidity of Euler flows. Preprint arXiv:1902.0631 (2019).
• 5T. Tao. Finite time blowup for an averaged three-dimensional Navier-Stokes equation. J. Amer. Math. Soc. 29 (2016), no. 3, 601-674.
• 6T. Tao. Searching for singularities in the Navier-Stokes equations. Nature Reviews Physics 1 (2019) 418–419.
• 7M. Freedman. P/NP, and the quantum field computer. Proc. Natl. Acad. Sci. USA 95 (1998) 98–101.
• 8E. Witten. Quantum field theory and the Jones polynomial. Comm. Math. Phys. 121 (1989) 351–399.
• 9C. Moore. Undecidability and Unpredictability in Dynamical Systems. Phys. Rev. Lett. 64 (1990) 2354–2357.
• 10S. Wolfram. Undecidability and intractability in theoretical physics. Phys. Rev. Lett. 54 (1985) 735–738.
• 11J.H. Reif, J.D. Tygar, A. Yoshida. Computability and complexity of ray tracing. Discrete Comput. Geom. 11 (1994) 265–288.
• 12H.T. Siegelmann, E.D. Sontag. On the computational power of neural nets. J. Comput. Syst. Sci. 50 (1995) 132–150.
• 13S. Wolfram. Undecidability and intractability in theoretical physics. Phys. Rev. Lett. 54 (1985) 735–738.
• 14I. Agol, J. Hass, W. Thurston. The computational complexity of knot genus and spanning area. Trans. Amer. Math. Soc. 358 (2006) 3821–3850.
• 15R. Cardona, E. Miranda, D. Peralta-Salas, F. Presas. Constructing Turing complete Euler flows in dimension 3. Proceedings of the National Academy of Sciences May 2021, 118 (19) e2026818118; DOI: 10.1073/pnas.2026818118.

CONCLUSIONS

Indécidabilité et chaos.

En raison de l'indécidabilité du problème d'arrêt des machines de Turing, une propriété importante d'un système dynamique complet de Turing est l'existence de trajectoires qui présentent un comportement indécidable à long terme. En effet, il est indécidable de déterminer si la trajectoire passant par un point explicite arrivera dans un ensemble ouvert explicite de l'espace, l'une des principales conséquences du résultat étant qu'il permet de prouver que certains phénomènes de l'hydrodynamique sont indécidables. Autrement dit, il n'y a pas d'algorithme pour garantir qu'une particule fluide traversera une certaine région d'espace dans un temps fini (en termes métaphoriques : si nous envoyons un message à l'intérieur d'une bouteille, nous ne pouvons pas garantir qu'il atteindra son destinataire). Cette incapacité à prédire, différente de celle établie par la théorie du chaos, peut être comprise comme une nouvelle manifestation du comportement turbulent des fluides. Dans la théorie du chaos, l'imprévisibilité est associée à l'extrême sensibilité du système aux conditions initiales - le battement d'ailes d'un papillon peut générer une tornade. Ici, nous prouvons qu'il ne peut y avoir aucun algorithme qui résout le problème, ce n'est pas une limitation de nos connaissances, mais de la logique mathématique elle-même.

Ordinateurs fluides théoriques  et le problème de Navier Stokes.

Tao a lancé un programme en 2016 basé sur la complétude de Turing des équations d'Euler pour résoudre le problème de l'explosion des équations de Navier-Stokes. La proposition de Tao, pour l’instant, spéculative, est d'utiliser un ordinateur fluide théorique pour forcer le fluide à accumuler de plus en plus d'énergie dans des régions plus petites, jusqu'à ce qu'une singularité se forme, c'est-à-dire un point où l'énergie devient infinie. Cependant, pour le moment, la manière de procéder est largement ouverte pour les équations d'Euler ou de Navier-Stokes.