Dossier de Arthur, du podcast Trajectoires

Ce dossier a été diffusé dans l’épisode 290 de Podcast Science à la suite de l’interview des membres du podcast Trajectoires.

Aujourd’hui, on va parler de calcul. Je vais vous donner des exemples, et je vais espérer que ça vous permettra de comprendre ce qu’est un calcul. On a plein de définitions formelles, mais ce n’est pas très intéressant en podcast.

Molécules

Je prends tout de suite un premier exemple. Je vais supposer que vous savez tous vaguement ce qu’est une molécule. C’est un ensemble d’atomes, tel qu’entre deux atomes, vous ayez un certain nombre de liaisons. Parfois, on a deux molécules, elles sont tellement grosses qu’on ne sait pas si c’est pas deux fois la même molécule, mais vu sous un autre angle. Alors, la question, c’est : est-ce que ces deux molécules sont identiques ?

Aparté, j’y connais que dalle en chimie. Mais ça n’empêche pas de s’en servir comme exemple. D’ailleurs, un informaticien peut très bien répondre à une question de scientifique sans savoir pourquoi il a besoin de cette réponse. Par contre, l’informaticien a besoin de savoir comment on va représenter cette molécule dans l’ordinateur. Ce n’est pas trop possible de faire une photo de molécule, pour autant que je sache, et c’est pas super pertinent. Donc on va supposer qu’on a juste l’ensemble des atomes, et puis le nombre de liaison entre chaque paire d’atome. On va dire qu’on se fiche de l’angle. Petite question, est-ce que selon vous, ou sur le chat, vous pensez qu’on peut trouver une méthode pour répondre à cette question. Y a-t-il une méthode pour dire si deux molécules sont les mêmes ou pas ?

Aparté/temps de réflexion

Le temps que vous réfléchissiez un peu, que vous vous demandiez comment on pourrait bien faire, je fais une remarque. Un informaticien ne dira jamais une méthode, mais un Algorithme. Ça veut dire la même chose, mais c’est plus formel. Dans la vie de tous les jours, si on demande une méthode, on pourrait vous dire : regarder si elles ont grosso modo la même forme, si vous trouvez que c’est allongé, alors déjà allongez les de la même façon. Mais tant qu’on a pas définit ce qu’était allongé, alors ce n’est pas un algorithme – ce n’est pas une méthode de calcul – parce que il n’y a pas de moyen de donner une intuition à l’ordinateur.

Alors ?

Réponse

Il y a une méthode. Déjà, si les deux molécules n’ont pas le même nombre d’atomes, vous savez que c’est pas la même molécule. Ensuite, vous retournez la première molécule de toutes les manières possibles. Pour rappel, on ne retourne pas la molécule physique, on retourne juste l’ordre des éléments. Si l’information était stockée dans un tableur, avec un atome par ligne, ça reviendrait juste à permuter l’ordre des lignes. Ce qui ne changerait pas la molécule, puisque les informations sur les liaisons bougeraient avec la position de l’atome dans votre tableau. Il y a un nombre fini de manière de réordonner vos atomes. Si à un moment votre première molécule retournée est égale à votre deuxième molécule, c’est gagné, c’est la même molécule, donc vous répondez oui. Sinon, vous répondez non, c’est qu’il s’agit de deux molécules différentes. Puisqu’on a pu calculer la réponse, un informaticien dira que le problème est calculable. Et c’est bon, les chimistes, problème réglé !

Efficacité

Euh… Est-ce que le problème est vraiment réglé ? Précisément, s’il y a n atomes, le nombre de manière de tourner la molécule est n x n − 1 x n – 2 x … x 2 x 1. C’est énorme, mais c’est fini. Donc en théorie, tout marche. Les gens ayant déjà programmé vont un peu râler en écoutant ma réponse. Parce que même si je ne vous ai pas menti, ce n’est pas calculable en pratique. Par exemple, le Buckminsterfullerène est une des plus grosses molécules gazeuses détectées dans l’espace à ce jour (trouvé en posant la question au moteur de recherche Lilo). Pour 60 atomes, le nombre de manière possible d’ordonner les atomes comporte 81 chiffres ! C’est-à-dire que si on avait commencé au big bang, en testant un milliard de milliard de milliard de milliard de milliard de milliard de milliard de combinaisons par seconde, on en serait à moins de deux pourcents de la fin du calcul.

Donc un vrai informaticien devra trouver des techniques pour tester en pratique beaucoup plus efficacement. Je vous donne quelques méthodes pour diminuer la taille de la recherche. Par exemple, vous pouvez regarder si les deux molécules ont le même diamètre, puisque le diamètre ne change pas quand on réordonne. Vous pouvez réordonner la molécule 2 pour qu’elle ai tous ses hydrogènes en premier, l’hélium en second, le lithium en 3ème… Bref, classer les atomes selon leur taille. Si votre molécule a plein d’atomes de types différents, vous gagnez plein de temps. Puis vous pouvez aussi trier selon le type de ses voisins.

Pour information, aujourd’hui, on a des méthodes qui permettent de trouver, en général, assez facilement la bonne permutation, qui montre que les deux molécules sont identiques. On a aussi des méthodes qui permettent en général de répondre rapidement que deux molécules sont différentes. Je dis en général, parce qu’on peut créer des paires de molécules qui se ressemblent assez pour que nos méthodes prennent beaucoup de temps. Même si c’est des molécules artificielles, créées seulement pour montrer que nos méthodes ne sont pas parfaites. Mais ça pourra faire l’objet d’une autre chronique.

Problème de l’arrêt

Je vais maintenant prendre un deuxième exemple. Même les non-informaticiens on peut-être déjà vu du code. Dans des films, pour faire impressionnant. Sinon, dans votre navigateur internet, tapez contrôle-u, ou pomme u, et vous verrez le code de la page que vous regardez. Notre problème étant donc : étant donné un code, c’est-à-dire une suite d’instructions quelconques, mais qu’on peut appliquer à la lettre, est-ce qu’à un moment, votre code va s’arrêter tout seul ?

Parfois, on ne s’arrête pas. Par exemple, si je vous dis de dire tous les nombres de 0 à l’infini, vous n’allez pas vous arrêter. Mais à l’opposé, si je vous demande si deux molécules sont identiques, vous allez vous arrêter, quelle que soit la paire de molécules. Mais en général ? Peut-on décider, étant donner une suite d’instruction, si elle va s’arrêter ?

Aparté : différence avec le problème précèdent

Ce problème s’appelle problème de l’arrêt. Et c’est le premier résultat d’informatique connu. On le doit à Alan Turing, dont vous avez peut-être déjà entendu parler. Dans son papier de 1936, il parle du problème que je vous pose. C’est-à-dire longtemps avant les premiers ordinateurs. Il introduit et définit la notion de calcul toujours utilisée aujourd’hui par les théoriciens.

Réponse

Je vous donne la réponse. D’abord, dire si le programme s’arrête, c’est simple. Vous lancez le programme, et vous attendez. Quand il s’arrête, vous répondez oui. Le problème, c’est que vous ne pouvez pas dire non. Parce que vous ne savez jamais combien de temps il faut laisser le calcul. On a envie de trouver des moyens de vérifier que le programme s’arrête avant même de lancer le calcul. En fait, il y a énormément de moyens de faire ça dans des cas particulier, et je vous invite à faire parler des gens qui s’intéressent à la vérification de programme, c’est passionnant !

Mais ce ne sont pas des moyens généraux. Il y aura toujours, soit des programmes que vous ne saurez pas analyser, soit des programmes sur lesquels votre analyse ne répondra pas. Ou répondra une chose fausse. Puisqu’on peut répondre oui, mais pas non, on dit que le problème est semi-décidable. Et c’est là tout l’intérêt de la calculabilité. Si on pouvait répondre à toutes les questions, alors ça n’aurait pas d’intérêt de se demander s’il y a une réponse ou pas. On chercherait juste à répondre efficacement. Ce domaine permet de dire aux chercheurs : arrêter de chercher une réponse, il n’y en aura pas. Cherchez plutôt à approximer, ou à résoudre des sous-problèmes.

Preuve

Je vais demander une minute aux auditeurs qui n’aiment pas les maths. J’ai très envie de faire la preuve qu’on ne peut pas répondre non à tous les coups. Elle n’est vraiment pas longue, pour une preuve mathématique de cette importance, et elle est même plutôt jolie.

Par l’absurde : on va supposer que c’est possible, que l’on a une programme qui est capable à tous les coups de nous répondre si oui ou non un programme donné va s’arrêter, et on va montrer que si on prend cette hypothèse, alors on arrive à une contradiction.

En langage plus mathématique, supposons qu’on ait inventé un programme P qui prend en entrée un programme x. Quel que soit le programme x, aussi complique soit il, P répond oui si  x s’arrête, et P répond non sinon. On va maintenant construire un programme un peu tordu, construit spécifiquement pour mettre en défaut notre hypothèse de départ.

Prenons Q, qui prend en entrée un programme y. Supposons que y prenne lui-même un argument. Q applique P à (y appliqué à y). Si P répond oui, alors Q ne s’arrête pas, sinon, si P répond non, alors Q s’arrête immédiatement. Appelons Q avec comme argument Q. Soit (Q appliqué à Q) s’arrête, soit il ne s’arrête pas. On étudie les deux cas.

Supposons que (Q appliqué à Q) s’arrête. Par construction, ça veut dire que P appliqué à (Q appliqué à Q) à répondu non, donc que (Q appliqué à Q) ne s’arrête pas. Contradiction.

Supposons maintenant que (Q appliqué à Q) ne s’arrête pas. Puisque P s’arrête, c’est que Q est rentré dans la boucle. Donc que P appliqué à (Q appliqué à Q) a répondu oui, donc que (Q appliqué à Q) s’arrête. Contradiction aussi.

Dans tous les cas on a une contradiction. Conclusion : il n’existe aucun programme P qui vérifie dans tous les cas si un programme s’arrête.

Génome

Je vous donne un dernier exemple, beaucoup plus court, que je trouve amusant. On vous donne un génome, et vous devez dire si c’est le génome d’un être vivant qui a existé sur terre avant le 1er janvier 2017, et non sinon. Selon vous, est-ce que ce problème est décidable ? Attention, il y a un piège. Si on regarde la calculabilité, c’est totalement décidable. En effet, il y a eu un nombre fini d’êtres vivants sur terre donc un nombre fini de génomes. Donc il suffit de comparer votre entrée à la totalité de ces génomes.

Ce genre de problème, c’est là où on se rend compte que on ne peut nous faire confiance que quand on vous dit “c’est impossible”. Parce que là, on va vous dire “c’est possible” (car calculable, donc décidable). Mais bien sûr, vous n’avez pas la liste des génomes des êtres vivants. Et bien sûr, vous n’avez pas de machine à voyager dans le temps pour aller les chercher. Et donc, je serai incapable de vous donner une méthode concrète pour répondre à cette question.

Mais.

Ce n’est pas parce que je ne peux pas vous donner la méthode que ça n’existe pas. C’est comme si vous me demandiez de vous donner le texte perdu d’un philosophe grec, ou l’intégrale du début de Dr Who. C’est perdu, personne pourra vous le donner, mais ça existe quand même. Et tant que ça existe, on va dire que le problème est décidable.

Conclusion

Pour conclure, je mentionne deux sujets que j’aime bien, et dont j’ai pas le temps de parler. D’abord, il existe des problèmes où on ne peut ni répondre oui, ni répondre non. Ni décidables, ni même semi-décidables. Tous les exemples que je connais sont très mathématiques, mais pas forcément très compliqués. Parce que la question, sinon, est simple : étant donné une phrase mathématique, avec des « il existe x tel que truc » ou « pour tout y, bidule », et puis des équations avec variables, additions et multiplication, est-ce que la phrase est vraie.

Ensuite, si un jour on découvrait une méthode qui réponde au problème de l’arrêt, que pourrait-on faire avec ? On sait que cette méthode ne sera pas implémentée par un ordinateur. Peut-être par la pythie de Delphes, qui sait ? En tout cas, on appelle ça un « oracle ». En tout cas, c’est quand on rajoute des oracles que la calculabilité peut vraiment devenir intéressante.