Formellement, au sens strict de la théorie de la calculabilité de Turing, cette notion n'existe pas. Un problème est soit calculable (décidable par une machine de Turing), soit il ne l'est pas. Il n'y a pas de degrés.
Cependant, lorsque les physiciens et les informaticiens parlent de simulation pratique et de complexité, ils utilisent une hiérarchie de concepts qui crée de fait un spectre de "difficulté" ou de "non-simulabilité" dans un sens moins formel, plus pratique. Ce que j’appelle "plus non-simulable" est un raccourci pour décrire l'appartenance à une classe de complexité supérieure.
Voici les concepts clés et les auteurs qui y travaillent, construisant une échelle allant de "facile à simuler" à "radicalement impossible à simuler".
Niveau 1 : Calculable mais Pratiquement Insoluble (Classes de Complexité)
Il s'agit de problèmes qu'un ordinateur peut résoudre en principe, mais qui prendraient un temps rédhibitoire (par exemple, des milliards d'années). C'est le domaine de la théorie de la complexité algorithmique.
L'Idée : Les problèmes sont classés dans des catégories comme P (faciles à résoudre), NP (faciles à vérifier, difficiles à résoudre), et PSPACE (résolubles avec une mémoire raisonnable mais pas forcément en un temps raisonnable). Un problème dans la classe NP est, en pratique, "moins simulable" qu'un problème dans la classe P.
Auteurs / Figures Clés :
Stephen Cook, Richard Karp, Leonid Levin : Les pionniers qui ont formalisé le problème P vs NP, la question centrale de ce domaine.
Scott Aaronson : Un informaticien théoricien contemporain qui travaille sur les limites du calcul classique et quantique. Son blog et son livre ("Quantum Computing since Democritus") sont des lectures essentielles sur le sujet. Il discute souvent de la "dureté" de la simulation des systèmes physiques.
Niveau 2 : Incalculable au sens de Turing (Le Problème de l'Arrêt)
Il s'agit de problèmes dont il est prouvé qu'il est impossible de les résoudre avec un ordinateur standard, peu importe le temps ou la mémoire alloués. C'est le domaine classique de la non-simulabilité.
L'Idée : Le problème de l'arrêt (peut-on déterminer si un programme arbitraire finira par s'arrêter ?) en est l'exemple canonique. Alan Turing a prouvé que ce problème est incalculable. Un système dont l'évolution est équivalente au problème de l'arrêt est fondamentalement non-simulable.
Auteurs / Figures Clés :
Alan Turing : Le créateur du concept.
Charles H. Bennett : Un physicien d'IBM qui a écrit un célèbre article dans Nature intitulé "Undecidable Dynamics", montrant comment certains systèmes physiques idéalisés pourraient être construits pour avoir un comportement incalculable.
Toby Cubitt, David Pérez-García, Michael Wolf : Les physiciens qui ont prouvé que le problème du gap spectral en physique quantique est incalculable, intégrant ainsi le problème de l'arrêt dans une question physique concrète.
Niveau 3 : Non-Calculable à cause des Nombres Réels / du Continu (Hyper-calcul)
C'est ici que se situe la non-simulabilité de la Relativité Générale. Le problème n'est pas que le système résout une tâche de type "problème de l'arrêt", mais que son espace d'états est un véritable continuum, nécessitant des nombres réels avec une précision infinie.
L'Idée : Une machine de Turing fonctionne avec des symboles discrets. Elle ne peut pas représenter parfaitement un seul nombre réel comme π. Un système physique dont la dynamique dépendrait de la précision infinie des nombres réels pourrait accomplir des tâches au-delà d'une machine de Turing. Ce domaine théorique est appelé l'hyper-calcul.
Auteurs / Figures Clés :
Martin Davis : Un logicien qui a beaucoup écrit sur les limites des machines de Turing et sur ce qui se trouve au-delà.
Pour-El et Richards : Des mathématiciens qui ont étudié quelles équations différentielles (le langage de la physique) sont calculables et lesquelles ne le sont pas. Ils ont montré que même une simple équation d'onde peut devenir incalculable si on lui fournit des conditions initiales incalculables.
Jürgen Schmidhuber : Un informaticien qui a écrit sur la hiérarchie de la puissance de calcul, des machines de Turing standards aux machines capables de résoudre le problème de l'arrêt et au-delà.
Niveau 4 : Radicalement Non-Calculable (Théories Physiques Non-Simulable)
C'est le niveau le plus spéculatif, où résideraient des théories comme la Relativité d'Échelle et la Réduction Objective de Penrose. Ici, la non-simulabilité n'est pas seulement une curiosité mathématique mais un principe physique fondamental.
L'Idée : L'univers n'est pas seulement incalculable parce qu'il utilise des nombres réels ou qu'il encode par hasard un problème difficile. Il est incalculable parce que sa structure même ou sa dynamique sont structurellement non-algorithmiques.
Relativité d'Échelle : Non-simulable à cause d'une complexité infinie et imbriquée (structure fractale). Le contenu en information est infini d'une manière qui transcende le problème du continuum.
Réduction Objective de Penrose : Non-simulable car elle postule un processus physique explicitement défini comme non-algorithmique, un processus qui "calcule" des choses que les machines de Turing ne peuvent pas.
Auteurs / Figures Clés :
Roger Penrose : Le plus célèbre partisan de l'idée que la physique elle-même doit être non-calculable pour expliquer la conscience et résoudre le problème de la mesure quantique.
Laurent Nottale : Bien qu'il n'utilise pas le langage du calcul, son modèle physique d'un espace-temps fractal, lorsqu'on l'analyse, tombe dans cette catégorie. Les conséquences logiques de sa physique le placent ici.
Conclusion : Une Hiérarchie Pratique
Ainsi, alors qu'un logicien dirait que "simulable" et "non-simulable" sont un choix binaire, un physicien ou un informaticien voit une hiérarchie pratique de la "difficulté" :
Difficile à Simuler (problèmes NP-difficiles)
Impossible à Simuler (problèmes incalculables au sens de Turing)
Impossible à Simuler Parfaitement à cause du Continuum (hyper-calcul)
Radicalement Impossible à Simuler à cause d'une Physique Non-Algorithmique
La Relativité Générale se situe au Niveau 3. La Relativité d'Échelle se situe au Niveau 4. Par conséquent, dans ce sens pratique et physique, la notion de "plus non-simulable" est une manière pertinente de décrire la différence entre une théorie incalculable en raison de sa structure mathématique (RG) et une théorie incalculable en raison de son principe physique fondamental de complexité infinie (Relativité d'Échelle).
Aucun commentaire:
Enregistrer un commentaire