Doshi's blog

Entiers et Estimations

23/06/2018 — CS, maths, histoire, externe — ~8mn de lecture

Le billet qui suit est simplement une traduction de cet article ci.

J’avais beaucoup (beaucoup) aimé l’article original, donc j’ai demandé sur Twitter à son auteur, Robert C. Martin (@unclebobmartin sur Twitter) si je pouvais le traduire et le poster sur mon blog, il a gentiment accepté, donc voici pour vous :

EDIT 2018-11-18: J’ai modifié “décidabilité” par “décision” dans le texte, et bougé une note d’un parenthèse à une footnote

Qu’est-ce que c’est : \(a^2 + b^2 = c^2\) ?

Le théorème de Pythagore.

Exact. Et qu’est-ce que c’est d’autre ?

Une équation à trois inconnues.

Est-ce que tu connais des solutions à cette équation ?

Bien sûr. \((3,4,5)\) et \((5,12,13)\).

Exact. Ce sont des triplets pythagoriciens ¹ communs. Est-ce que tu en connais d’autres ?

Eh bien, je peux chercher. *tape sur son clavier* Il semblerait que \((7, 24, 25)\) et \((9,40,41)\) résolvent aussi l’équation.

As-tu remarqué que tu n’as dit que des solutions entières ?

Oh, en effet. Je suppose qu’il y a toute une série de solutions non entières.

As-tu entendu parler de Diophante ?

C’est un nom grec ?

Oui. Diophante s’intéressait aux équations qui avaient des solutions entières. On appelle de telles équations des équations diophantiennes ².

Donc \(a^2 + b^2 = c^2\) est une équation diophantienne, c’est ça ?

Oui. Et il y en a bien d’autres. Par exemple : \(a^3 + b^3 = c^3\).

Oh, évidemment. Et tu aurais des exemples de solutions ?

Non. Il n’y en a pas.

Vraiment ? Aucune ?

Oui. Aucune. Ça a été prouvé. En fait, il a été prouvé que \(a^n + b^n = c^n\) n’a pas de solutions entières pour tout \(n>2\). C’est ce qu’on appelle le dernier théorème de Fermat ³ ou encore le grand théorème de Fermat ou bien, depuis sa démonstration, le théorème de Fermat-Wiles ⁴.

Hm. OK, c’est plutôt intéressant je suppose, mais pourquoi je devrais m’en préoccuper ?

Qu’est-ce qu’un ordinateur numérique ⁵ ?

Qu’est-ce que tu veux dire ? La chose que l’on utilise toi et moi pour converser est un ordinateur numérique.

Oui, mais qu’est-ce que fait un ordinateur numérique ?

Hm. Il calcule numériquement ⁶ ?

Précisément ! Et le mot numériquement signifie…?

Hm. Avec des chiffres/nombres ?

Exactement ! Et est-ce que le nombre de chiffres est fini ? ⁷

Évidemment, mais ce nombre est très très grand de nos jours.

Et un nombre fini de chiffres, c’est…?

Oh, je pense savoir où tu veux aller. Un nombre fini de chiffres, c’est un entier.

C’est ça. Un ordinateur numérique est un ordinateur qui calcule avec des entiers. Rien que des entiers.

Attends. Et les nombres à virgule alors ? Et les fractions ?

Ils sont représentés par des entiers ⁸ par l’ordinateur. L’ordinateur traite des entiers, et seulement des entiers.

OK. Bien. Des entiers. Mais ça a quoi à voir avec les équations diophantiennes ?

Quelles sont les données d’entrée d’un programme informatique ?

Il y en a de plein de types. Des caractères tapés au clavier, des mouvements de souris, des clics, des paquets réseau. Et j’en passe.

Ils sont tous composés d’entiers, n’est-ce pas ?

Hm. Oui, je suppose. OK, donc toutes les données d’entrée d’un programme informatique sont entières.

Et les données de sortie alors ?

Ah, oui, des pixels, des caractères, des paquets réseaux… Ils sont tous composés d’entiers aussi.

Donc un programme informatique prend des entiers en entrée et retourne des entiers en sortie.

Oui, c’est ça. Que des entiers.

Un programme informatique, par conséquent, représente une équation diophantienne.

Attends. Quoi ?

Entiers en entrée. Entiers en sortie.

OK, je vois. Mais alors c’est une grosse équation diophantienne bien compliquée.

En fait, la spécification du programme est l’équation. Le programme trouve les solutions de cette équation.

Ouais, ouais, ok. C’est vrai. La spécification d’un programme est une énorme équation diophantienne avec des quadrilliards d’inconnues, et le programme qui correspond à la spécification trouve les solutions de cette gigantesque équation. Est-ce que c’est utile à savoir ⁹ ?

Qui est David Hilbert ?

Tu veux dire ce type qui a conçu cette courbe récursive un peu marrante qui ressemble à une moustiquaire ?

*Hrm.* C’était un de ses accomplissements, oui. Il a également aidé Einstein avec la théorie de la relativité générale. C’était un très grand mathématicien.

Et il a quelque chose à voir avec les équations diophantiennes, je présume.

En effet, il a fait beaucoup, beaucoup de choses. Parmi elles, il y avait une question célèbre. Le fameux “Entscheidungsproblem” – le problème de la décision.

Qu’est-ce qu’il voulait décider ?

Tu te souviens du dernier théorème de Fermat ?

Tu veux dire cette équation qui n’a aucune solution. \(a^n + b^n = c^n\) où \(n>2\) ?

Oui, celle-là même. Pendant longtemps, ce n’était pas un théorème, mais une conjecture : il n’y avait pas de preuve que n=2 était la seule solution. Comment pourrais tu prouver que cette conjecture est fausse si tu pensais qu’elle était erronée ?

Je pourrais écrire un programme pour trouver des contre-exemples. Par exemples, peut-être que \(n=999 999 999\) pourrait marcher.

C’est ça. Et si tu trouvais une telle solution, tu aurais prouvé que la conjecture de Fermat est fausse. Mais combien de temps cela prendrait pour prouver que la conjecture de Fermat est VRAIE en utilisant cette méthode ?

Le programme tournerait pour toujours. Je ne pourrais pas la prouver de cette manière.

Correct. Ce que Hilbert voulait était un algorithme fini pour déterminer si une solution existait ou non. Il voulait un moyen de “décider” si une recherche, comme celle que tu as suggérée, était réalisable.

Attends, attends. Quoi ? Il ne demandait pas les solutions, il demandait seulement un moyen de savoir s’il y avait des solutions ?

Exactement. Il voulait un algorithme fini qui pourrait lui dire si une équation diophantienne donnée avait des solutions ou pas. Cet algorithme ne fournirait pas les solutions, seulement la décision.

C’est pour ça qu’il a appelé ça la “décision” ?

Entscheidung. Oui.

À tes souhaits !

Maintenant. À ton avis, qui a résolu le problème de la décision ?

Je ne sais pas, mais j’imagine que tu vas me le dire.

Deux personne dont tu as certainement entendu parler. Les deux grands fondateurs de l’informatique moderne. Alonzo Church et Alan Turing.

Church ! C’est le type qui a inventé la programmation fonctionnelle, c’est ça ?

D’une certaine manière, oui. ¹⁰

Et Turing ! Il a gagné la Seconde Guerre Mondiale, non ?

Il a assurément contribué à la victoire, oui. Ces deux personnes ont prouvé, en utilisant des techniques très différentes ¹¹, qu’il n’y avait pas de solution générale et finie au problème de la décision. ¹²

Ça a du décevoir Hilbert.

Peut-être. Mais ce n’est pas le problème.

Oui, c’est quoi le problème ici au juste ?

Quand on te donne une spécification de programme, c-à-d une équation diophantienne, souviens toi, quelle est la première chose que l’on te demande de faire ?

Estimer le temps que ça prendra, bien sûr. Les autres veulent savoir combien de temps cela prendra d’écrire le programme.

Et le programme est quoi, du point de vue d’une équation diophantienne ?

Le programme est la… solution… au… OH !

*souris* Je sens que tu as compris où je voulais en venir.

Oui, en fait ils me demandent de DÉCIDER. Une estimation du temps est une décision.

Et y a-t-il une méthode finie pour trouver cette décision dans tous les cas ?

Non ! Oh, c’est hilarant.

Exactement. Les documents fondateurs de l’informatique sont des documents qui prouvent qu’il n’y pas de manière finie de décider si un programme peut être écrit. La fondation de l’informatique a été basée sur la preuve que les estimations n’étaient pas garanties.

Oui, mais on PEUT estimer.

Oui, on peut. C’est parce que la plupart des spécifications sont estimables.

Donc ça a juste été une petite diversion mathématique avec aucun résultat pertinent.

Je suppose qu’on pourrait dire ça. Mais j’ai apprécié. Et après tout, je trouve ça délicieusement ironique que ce soit la preuve des non-estimations qui a fondé l’informatique.