Dedekind D(9) : compter les fonctions logiques, deux fois

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Je suis vraiment ravie de lancer cette nouvelle plongée dans les sources du jour parce qu'on a un sujet absolument incroyable. Salut Evelyne. Ah

Intervenant 20:10

ouais, incroyable, le mot est faible. C'est un vrai thriller qu'on a

Intervenant 10:15

là. Totalement. Imaginons un instant un problème mathématique d'une ampleur tellement colossale, tellement démesurée que la plus grande menace pesant sur sa résolution ne serait pas une simple erreur humaine.

Intervenant 20:28

Non, ce serait une particule

Intervenant 10:30

invisible ? Ouais, c'est ça. Un rayon cosmique qui aurait voyagé à travers l'espace intergalactique juste pour venir frapper un processeur en plein calcul sur Terre.

Intervenant 20:39

C'est fou quand on y pense.

Intervenant 10:41

Cette plongée explore un véritable monstre. On ne parle pas d'une petite équation qu'on réseau tranquillement sur un tableau noir, on parle d'une suite de nombres si insaisissables qu'il a fallu plus d'un siècle d'efforts acharnés pour en calculer seulement le neuvième terme.

Intervenant 20:54

Ouais, et pour poser d'emblée l'échelle de ce vertige, ce fameux neuvième terme n'a absolument rien d'ordinaire.

Intervenant 11:01

Ah bah tu m'étonnes !

Intervenant 21:02

C'est un nombre qui comporte très exactement 42 chiffres. Il commence par 286, il s'étire ensuite sur une myriade de combinaisons qui défient totalement l'entendement, pour finalement se terminer par 366.

Intervenant 11:15

C'est ce qu'on appelle dans le jargon de l'encyclopédie en ligne la suite A000372.

Intervenant 21:21

Exactement, A000372, une référence bien connue de ceux qui fréquentent le site de Nils Sloan.

Intervenant 11:27

Une suite qui donne des sueurs froides aux mathématiciens depuis 1897, carrément fin du siècle. La mission d'aujourd'hui, c'est de comprendre pourquoi ce simple calcul déclenche une explosion d'une telle violence, enfin une violence mathématique, qui met à genoux les ordinateurs les plus puissants du

Intervenant 21:45

monde. Et de voir comment on a fini par débusquer ce neuvième nombre l'année dernière.

Intervenant 11:51

Et bien sûr, pourquoi ce fameux rayon cosmique a failli tout faire dérailler à la toute dernière minute. Bon, décortiquons un peu tout ça. Qu'est-ce que ces nombres essaient de compter exactement ? Parce qu'on n'est pas en train de compter des pommes ou des galaxies, là.

Intervenant 22:04

Non, pas du tout. On compte des objets purement logiques. Tout le mystère repose sur ce qu'on appelle les fonctions logiques croissantes.

Intervenant 12:11

D'accord.

Intervenant 22:12

Et pour bien visualiser, il faut plonger dans l'univers des bouléens.

Intervenant 12:15

Les fameux bouléens. C'est vraiment la brique de base absolue de notre technologie, ça. Si l'on veut comprendre pourquoi tout cela est crucial, il suffit de penser au smartphone ou à l'ordinateur qui diffuse cet audio en ce moment même.

Intervenant 22:29

Exactement. Tout fonctionne avec ça.

Intervenant 12:31

Tout, au niveau microscopique, fonctionne avec des booléens. En gros, une variable booléenne, c'est juste un interrupteur. Soit c'est vrai et on lui donne la valeur 1, soit c'est faux et on lui donne la valeur 0.

Intervenant 22:42

C'est la base de l'informatique, ouais. Et une fonction logique, c'est simplement une machine abstraite. Elle prend plusieurs de ses variables en entrée, plusieurs interrupteurs si tu préfères, elle mouline tout ça et elle recrache un seul résultat à la sortie, 0 ou 1.

Intervenant 12:57

Jusque là, c'est simple.

Intervenant 22:58

Voilà. Mais le mot central de notre énigme, c'est le terme « croissante ».

Intervenant 13:03

Attends, comment on définit la croissance dans un univers où il n'y a que des 0 et des 1 ? Je veux dire, il n'y a pas beaucoup d'espace pour grandir là-dedans.

Intervenant 23:11

Ah, c'est là qu'est l'astuce. La règle de croissance est super stricte. Si l'on modifie les entrées en ne faisant que monter des interrupteurs de 0 vers 1, le résultat final de la fonction ne peut jamais faire le mouvement inverse.

Intervenant 13:23

Donc, il ne peut pas passer de 1 à 0.

Intervenant 23:26

Tout à fait. Si la sortie était à 0, elle peut passer à 1 ou rester à 0. Mais si elle était déjà à 1, elle y reste. Elle ne peut pas redescendre.

Intervenant 13:34

Ah ouais, je vois. Pour rendre ça plus tangible, on pourrait imaginer un système de sécurité avec des capteurs sur les fenêtres d'une

Intervenant 23:40

maison. Très bon exemple.

Intervenant 13:42

Si le système est déclenché, donc elle est à 1, et que l'alarme sonne, le simple fait d'ouvrir une fenêtre supplémentaire, donc de faire passer un autre capteur de 0 à 1, ça ne doit jamais éteindre l'alarme.

Intervenant 23:54

Exactement. Ce serait stupide d'ailleurs.

Intervenant 13:56

L'état global ne peut que stagner ou augmenter vers 1. Il ne peut jamais régresser vers le faux. C'est ça une fonction croissante.

Intervenant 24:03

C'est parfaitement résumé. Et c'est en 1897 que le mathématicien allemand Richard Dedekind pose la question fatidique. Qui est ? Il se demande, si l'on a un nombre n de variables en entrée, combien de ces fonctions logiques croissantes différentes on peut inventer ?

Intervenant 14:21

Dit comme ça, ça a l'air d'être un petit casse-tête du dimanche

Intervenant 24:23

après. C'est ce que beaucoup ont cru au début. Mais la réalité est beaucoup plus brutale. Ce qui est fascinant ici, c'est la mécanique de cette croissance.

Intervenant 14:31

C'est-à-dire ?

Intervenant 24:32

Prenons n variables en entrée. Il y a 2 puissance n configurations de départs possibles. Par exemple, avec 3 interrupteurs, on a 2 puissance 3, donc 8 combinaisons possibles de positions.

Intervenant 14:44

D'accord, donc de 0, 0, 0 jusqu'à 1, 1,

Intervenant 24:47

1. Voilà. Ensuite, pour chacune de ces huit configurations, la fonction doit attribuer un résultat final, 0 ou 1.

Intervenant 14:55

Ok, je te suis.

Intervenant 24:55

Ce qui porte le nombre total de fonctions imaginables, et ça c'est avant même de vérifier si elles sont croissantes, à 2 puissance 2 puissance n.

Intervenant 15:04

Waouh, attends. 2 puissance 2 puissance n. Il faut vraiment s'arrêter là-dessus parce que le cerveau humain n'est pas du tout câblé pour comprendre une double exponentielle.

Intervenant 25:13

C'est clair, ça grimpe vite.

Intervenant 15:15

Faisons le calcul de base. Si n vaut 2, on a deux variables. 2 puissance 2, ça fait 4 configurations en entrée. Et 2 puissance 4, ça fait 16 fonctions possibles au total.

Intervenant 25:26

C'est ça.

Intervenant 15:27

Et parmi elles, on retire celles qui ne respectent pas notre fameuse règle de l'alarme, donc celles qui ne sont pas croissantes, et il en reste six. Donc le nombre de dedekind pour deux, qu'on appelle dedekind, c'est six.

Intervenant 25:37

Ouais, c'est facile, on peut dessiner les six possibilités sur un coin de table ou un post-it.

Intervenant 15:41

Mais regardons l'accélération, c'est là que ça devient effrayant en fait. Si on passe à D5, juste 5 misérables petites variables. Ouais,

Intervenant 25:50

un catérupteur.

Intervenant 15:51

2 puissance 5, ça donne 32 configurations. Mais le nombre total de fonctions à tester explose à 2 puissance 32.

Intervenant 25:59

Ce qui nous fait plus de 4 milliards.