ou la vie quotidienne d'un chercheur à Tokyo

Calculer l’incalculable

Peu de gens ont conscience que les ordinateurs ne peuvent pas tout calculer. C’est en effet un résultat bien connu dans mon domaine de recherche : la machine de Turing, modèle théorique des ordinateurs, a des limites bien déterminées en terme de potentiel calculatoire, c’est-à-dire qu’il y a des problèmes que les ordinateurs ne peuvent calculer et ne sauront jamais résoudre.

Par exemple, considérons le problème de décider si une formule arithmétique (donc avec des variables « x, y, z, … »,  les symboles « +, -, *, /, = », les entiers relatifs et les quantifications « pour tout, il existe ») est vraie ou fausse. Plus concrètement si je prends la formule « pour tout x, il existe y tel que y = x+1 », celle-ci est clairement vraie : vous prenez n’importe quel nombre, il existe toujours un nombre un cran au dessus. Par contre la formule « pour tout x et tout y, il existe z tel que x = y * z » est faux, car si vous prenez x=1, y=2 par exemple, il n’existe aucun entier relatif z tel que 1 est égal à 2 fois z. Et bien le problème de décider si une formule arithmétique est vraie ou fausse est un problème indécidable, c’est-à-dire qu’un ordinateur est incapable de trouver une solution à ce problème. Ce n’est pas une question de puissance, c’est une question de faisabilité : il n’existe pas de méthode automatique pour résoudre ce problème en temps fini, donc un ordinateur ne pourra jamais y répondre.

Jamais ? Pas sûr. Des gens bien barrés ont étudié cette question de l’incalculable sous un angle… je dirai… original.

Dans la famille « je-prends-une-dose-de-LSD-à-tuer-un-cheval-et-ensuite-je-fais-de-la-science », je demande Malament, Hogarth, Etesi, Németi et Welch. Ces gens-là ont démontré des résultats ENORMES ! En voici un extrait.

Le temps n’est pas un long fleuve tranquille qui s’écoule uniformément. C’est une dimension non-normée dans le sens où le temps ne s’écoule pas pareil suivant les situations. Cet écoulement est relatif à un repère donné ; c’est ce que nous explique le principe de relativité générale d’Einstein.

Malament et Hogarth ont défini ce qui s’appelle maintenant les espaces-temps de Malament-Hogarth. Il s’agit d’espaces-temps où il existe une trajectoire infinie lamba telle qu’il existe un évènement p sur cette trajectoire où tous les évènements de lamba y sont antérieurs (alors que lamba est infini, je le rappelle). Ça veut dire qu’on a une suite infinie d’évènements, mais dans cette suite il y a un évènement qui succède à tous les évènements. Bon, déjà ça, c’est pas un résultat pour les mous du slip.

Hogarth avait déjà démontré en 1994 qu’il existait un espace-temps de Malament-Hogarth dans lequel un ordinateur pouvait calculer la décision de l’arithmétique, mais sans en exhiber d’exemple. C’est ce que font  Etesi et Németi dans cet article de 2002, où ils démontrent qu’un tel espace-temps de Malament-Hogarth est présent autour d’un trou noir en rotation et à charge électrique nulle, appelé trou noir de Kerr. Ainsi, un ordinateur ordinaire en orbite autour d’un tel trou noir, tournant autour tel une bille dans le lavabo sans jamais tomber dans le siphon, pourrai calculer notre problème pendant un temps infini pendant que nous, utilisateur, nous récupérions le résultat de ce calcul infini (le fameux évènement p où tout calcul serait antérieur). Ceci est théoriquement possible puisque l’écoulement du temps autour du trou noir serait nul, comme gelé, aux yeux d’un observateur extérieur, laissant ainsi infiniment de temps pour laisser l’ordinateur finir son calcul. Petit revers de la médaille, si j’ai bien compris pour accéder à cet évènement p dans cet espace-temps de Malament-Hogarth, il faudrait que l’utilisateur tombe dans le trou noir, ce qui risque d’engendrer quelques séquelles. De plus, ce résultat (car c’est pas du flan, ça a été démontré quand même) néglige les phénomènes d’évaporation du trou noir qui voit sa masse diminuer ou augmenter en fonction de la quantité de radiations émises et de rayonnements électromagnétiques absorbés.

Mais Welch va plus loin dans le craquage du slip scientifique : dans cet article de 2006, il présente deux résultats sidérants. Il démontre en effet que 1) pour tout prédicat hyper-arithmétique P  sur les entiers naturels, il existe un espace-temps de Matament-Hogarth dans lequel toute requête du type « n appartient-il à P ? » est calculable, et 2) pour tout espace-temps de Matament-Hogarth, il existe un ordinal dénombrable majorant la compléxité de l’arithmétique dans la hiérarchie de Borel. Autrement dit, dans tout espace-temps de Matament-Hogarth, l’arithmétique dans la hiérarchie de Borel est non seulement décidable, mais elle l’est en temps constant !

Je sais que vous panez rien. Rassurez-vous, moi non plus je ne capte pas grand chose de ces résultats. Mais je trouve ça énorme que des mecs se perdent dans de folles élucubrations et arrivent quand même à y prouver des résultats théoriquement justes ! Y’a pas à dire, la théorie, c’est beau.

Publicités

Commentaires sur: "Calculer l’incalculable" (9)

  1. Comme tu dis la théorie, c’est beau !
    Mais, cette théorie pourra-t-elle se voir un jour illustrée ?
    La majorité des pauvres mortels sont comme Saint Thomas « Je ne crois que ce que je vois » :p
    J’ai toujours trouvé les mathématiques fascinantes et encore plus quand il devient un outil pour démontrer des choses appartenant à d’autres domaines que le sien à priori. Mais il ne faut pas oublier que les hypothèses sont importantes dans une théorie démontrable :p
    En un sens, je trouve que les mathématiques naviguent entre « sciences occultes » et « sciences lumières »

  2. Dire que des personnes intelligentes perdent un temps significatifs pour prouver et publier des résultats, peut-être justes, mais parfaitement inutiles.

    Vive les sciences fondamentales, ou comment alimenter le discrédit sur des disciplines pourtant important qui n’ont déjà pas bonne presse ! Après on s’étonne que les gouvernement ne subventionne que la recherche appliquée…

  3. Haha, réactions intéressantes. Je ne suis pas du tout d’accord avec ton commentaire, Seb, et dans une moindre mesure avec ton commentaire, Ketty. Laissez-moi vous expliquer pourquoi.

    Comment peut-on savoir que ces résultats sont inutiles ? On ne peut pas ; personne ne le sait. Même les auteurs de ces articles n’en ont aucune idée. Et c’est normal, car c’est comme ça que fonctionne la recherche.

    Tournons-nous brièvement vers le passé. Dans les années 30, un jeune homme, un Anglais en plus, s’est posé les questions suivantes : « qu’est-ce qu’une fonction calculable ? Qu’est-ce qui la caractérise ? ». Les réponses à ces questions plus philosophiques que mathématiques ont conduit à la machine de Turing. Il était impossible à l’époque de prédire que ces résultats ultra-théoriques et à la limite du « raisonnable » allaient conduire à la révolution informatique que le monde a connu quelques dizaines d’années plus tard.

    Autre exemple : Galois, au début du 19ème siècle, travailla en algèbre sur la résolution des équations. Au lieu de chercher directement à résoudre ces équations, il étudia les groupes de racines possibles d’une équation et en déduit le mécanisme exact de la résolution par radicaux d’une équation de n’importe quel degré. De la folie pure à l’époque, et du jamais vu d’un point de vue complexité théorique. Ces travaux n’ont été compris de ces paires que 30 ans après sa mort, et ont complètement refondé l’algèbre !

    Plus tard, Hilbert développa une généralisation de l’espace Euclidien à un nombre arbitraire de dimensions, nommé aujourd’hui les espaces de Hilbert. Potentiellement, ces espaces peuvent avoir une infinité de dimensions (relisez cette phrase, et essayez d’imaginer ce que ça peut donner). A quoi un objet mathématique aussi théorique et qui n’existe clairement pas dans « le monde réel » peut-il bien servir ? Et bien, par exemple, à faire de la classification automatique : quand on a un ensemble de donnée que l’on cherche a automatiquement classifier sous des labels, on est incapable de la faire dans les espaces classiques que forment ces données. Par contre en plongeant l’ensemble de ces données dans un espace de Hilbert avec une infinité de dimension, on arrive facilement à faire la classification qui reste stable lorsque l’on revient travailler sur l’espace d’origine.

    Allez, un dernier : la théorie des cordes en physique. L’une des théories des cordes (car il y en a plusieurs en fait) a besoin d’un univers à 26 dimensions pour avoir une cohérence mathématique ! 26 ! Ca parait fou, mais pourtant c’est peut être bien comme ça que fonctionne notre univers.

    En plus du fait qu’il est impossible, pour quiconque, de savoir si une théorie aura ou non une utilité pratique, on peut ajouter le fait qu’il y ait des effets de bords dans la recherche fondamentale. Bien souvent, pendant que l’on cherche quelque chose, on trouve autre chose sur la route. Ainsi pour reprendre l’exemple de la théorie des cordes, c’est en bossant dessus que l’on a trouvé en mathématique le principe de symétrie-miroir des espaces de Calabi-Yau.

    Faire de la recherche, c’est chercher là où personne n’a cherché auparavant. La créativité et l’imagination sont des qualités essentielles, et c’est par des travaux très originaux que viennent les plus grandes avancés. Et bien souvent, dans leur temps, ces travaux paraissaient incongrus, pour ne pas dire farfelus et futiles. De plus, mais il s’agit là d’une conviction personnelle, toute recherche fondamentale, aussi théorique qu’elle soit, trouve tôt ou tard une application. C’est du moins ce que je constate quand je vois que des choses follement abstraites trouvent directement ou indirectement une « utilité » dans le monde des mortels. Je met « utilité » entre guillemets car pour beaucoup de gens, est utile ce qui peut être employé à une fin concrète. Ce n’est pas ma définition.

  4. Bon, ben j’vais reprendre des moules moi…

  5. Concernant, la recherche fondamentale et appliquée, on a un exemple sous les yeux: la relativité a été une nouveauté conceptuelle monstrueuse, sortie de l’esprit d’Einstein sans aucune expérience pour valider dans l’immédiat. Les expériences n’ont pas trop tardé, avec je sais plus quelles mesures d’évenement astronomique (la courbure de la lumière lors d’une eclipse, peut etre), et ont montré que la relativité modélise effectivement le réel, et est donc bien utile quand on traite des phénomènes à grande échelle (astronomie).

    Après, la relativité a mené à de la recherche sur les formes possibles d’espace-temps (déja Godel s’y était mis). Tout cela est très sexy car permet de spéculer sur le voyage dans le temps, etc.

    Concernant l’application de la relativité du temps à l’informatique, je trouve ça peu étonnant conceptuellement, et prématuré dans la mesure où effectivement ça ne sert à rien (puisque l’information obtenue dans l’échelle de temps accélérée ne peut voyager assez vite vers l’échelle de temps de l’utilisateur). Cela ne veut pas dire pour autant que la recherche en physique théorique sur le temps soit une perte de temps ;)

  6. Effectivement, j’ai deja utilise pas mal d’espaces avec les SVMs pour faire une reconnaissance faciale. Et j’etais bien content que quelqu’un ait invente ca, parceque bon resoudre des equations dans un espace a plus de 30 dimensions^^;

  7. Eusebe a dit:

    C’est grâce à des gens comme ça qu’on est sûr de ne pas être très intelligent, finalement. Ni très tordus :-)

  8. Mycroft a dit:

    Bouge pas Billx, je t’amène les frites…

  9. Olivier a dit:

    Ah ouais j’avais entendu parler du craquage des machines de Turing qu’on balance dans les trous noirs. Je vois un autre problème pratique : parler de décidabilité/calculabilité d’un problème/d’une fonction n’a de sens que si l’ensemble de ses instances/son domaine est infini. Donc il faut que la bande de la machine de Turing soit de taille non bornée et il va falloir m’expliquer comment on fait ça sans supposer que la matière est en quantité infinie dans l’univers.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :