Comment multipliez-vous ?

Que vaut $3\times 5$ ? Que vaut $159\times 423$ ?

Ces deux questions sont semblables : elles parlent de multiplication. En revanche, les méthodes que vous adopteriez pour y répondre sont très différentes. Dans le premier cas la réponse est immédiate car inscrite dans les tables de multiplication, bien ancrées dans votre mémoire ! En revanche dans le deuxième cas, pour obtenir le résultat il faut appliquer l’algorithme de multiplication (tout aussi bien ancré dans votre mémoire !) [1].

Mais au fait, qu’est-ce que la multiplication ? On peut l’imaginer comme une table infinie contenant, pour toutes les entrées $a$ et $b$, la valeur du produit $a\times b$. On dit qu’on la décrit par extension :

«LA» table de multiplication.

Mais en pratique on ne peut ni représenter ni mémoriser entièrement cette infinité d’informations. C’est à cela que sert l’algorithme [2] : on peut le décrire simplement, le mémoriser, et il permet de retrouver cette table infinie, case par case. L’algorithme de multiplication est un objet fini permettant de représenter la table de multiplication, un objet infini. Il s’agit d’une description par compréhension.

Représentation finie ou infinie

Oublions maintenant la multiplication et considérons le cas d’une fonction quelconque, que nous nommerons $f$ par exemple, associant à chaque entier naturel $n$ (qui peut donc valoir $0,1,2,3,\ldots$) un entier naturel $f(n)$ (la multiplication est une fonction à deux arguments, par souci de simplicité nous considérons désormais des fonctions à un argument). Le problème qui nous intéresse ici est celui de la représentation : cette fonction peut être représentée au moyen d’une table, infinie, ou d’un algorithme, qui est un texte fini. Un utilisateur ayant besoin de cette fonction consultera la table ou bien exécutera l’algorithme sur les entrées de son choix.

En voici une illustration dans le cas de la fonction $g$ qui teste si son entrée est un nombre premier [3] :
\[ g(n)=\begin{cases} 1&\text{si }n\text{ est un nombre premier,}\\ 0&\text{sinon.} \end{cases} \]

Deux représentations de la fonction $g$
	Premier(n) Si n < 2 alors renvoyer 0, Sinon d ← 2, Tant que d*d <= n faire : Si d divise n alors Renvoyer 0, Sinon d ← d+1. Renvoyer 1.
Une représentation infinie, par extension : la spirale d’Ulam	Une représentation finie, par compréhension : l’algorithme donné sous forme de «pseudo-code» qui étant donné un entier $n$, renvoie $1$ si $n$ est premier, $0$ sinon

Premier(n)
Si n < 2 alors renvoyer 0,
Sinon
    d ← 2,
    Tant que d*d <= n faire :
        Si d divise n alors
            Renvoyer 0,
        Sinon d ← d+1.
    Renvoyer 1.

Mais cela soulève une question : les deux représentations sont-elles interchangeables, au sens où elles fourniraient exactement la même information sur la fonction ? Exécuter l’algorithme pour retrouver la table suffit-il à exploiter la connaissance de l’algorithme, ou le contenu de cet algorithme nous renseigne-t-il plus ?

C’est une question vague, interprétable de multiples façons. Dans cet article nous allons présenter des réponses à une formulation bien précise de cette question. Imaginons un jeu où l’on nous pose une question sur une fonction donnée. L’accès que nous avons à cette fonction est ou bien une table de ses valeurs, ou bien un algorithme.

Peut-on répondre correctement aux mêmes questions selon que l’on dispose de l’une ou de l’autre de ces deux représentations?

Insistons sur le fait qu’on nous demande de toujours donner la bonne réponse, c’est-à-dire d’avoir une stratégie systématique permettant d’être sûr d’avoir toujours juste. Cette stratégie n’a pas à être efficace : on a tout le temps que l’on souhaite pour élaborer notre réponse (alors qu’en pratique, le choix de la représentation en programmation est souvent dicté par des critères d’efficacité).

Dans cet article nous allons voir que selon ce que l’on veut savoir sur la fonction, les deux représentations peuvent être ou non équivalentes. Pour acquérir une première intuition, vous allez faire l’expérience au moyen de jeux simples : étant donné un algorithme, il s’agira pour vous de deviner des propriétés de la fonction qu’il calcule dans chacun des deux cas suivants :

1. Vous n’avez pas accès au contenu de l’algorithme, mais vous pouvez l’exécuter, ce qui revient à consulter une table des valeurs de la fonction.
2. Vous avez accès au texte de l’algorithme lui-même.

Une première différence

Avant de jouer, quelques remarques simples.

À partir d’un algorithme on peut retrouver petit à petit la table des valeurs de cette fonction, en exécutant l’algorithme successivement sur chaque entrée possible.

Et inversement ? Peut-on, en consultant la table infinie, concevoir un algorithme calculant la fonction, un peu comme dans le test «Complétez la suite logique» ? Eh bien, on peut essayer de deviner, de proposer un tel algorithme, cependant on ne peut jamais être sûr que c’est le bon. En effet, il existe une différence importante entre les deux représentations, liée au fait qu’à tout instant l’on ne peut avoir lu qu’une quantité finie de données. Cela a la conséquence suivante :

• Dans le cas où l’on a accès à une table infinie recensant les valeurs de la fonction, à chaque instant on ne connaît les valeurs de cette fonction que sur un nombre fini d’entrées donc la fonction n’est jamais uniquement déterminée : à tout moment un tricheur pourrait, sans que l’on s’en aperçoive, changer la fonction en modifiant les entrées de la table encore non lues.
• Dans le cas où l’on dispose d’un algorithme calculant la fonction, celle-ci est uniquement déterminée dès que l’on a entièrement lu l’algorithme, fini par définition. Dans ce cas un tricheur ne pourrait changer la fonction qu’en modifiant l’algorithme et serait vite repéré.

Avoir le texte d’un algorithme est donc plus fort, semble ainsi donner plus d’information sur la fonction, que de pouvoir lire une table pour cette fonction. Est-ce vraiment le cas ? Quelles questions supplémentaires peut-on trancher si on connaît l’algorithme et pas seulement la table ? Quelle information faut-il rajouter à la table pour égaler l’algorithme ?

Jeux simples

Commençons à jouer. Une fonction, nommée par exemple $f$, vous est donnée sous la forme d’une table. Vous pouvez connaître les valeurs de cette fonction sur toutes les entrées de votre choix (pour cela, cliquez sur la case du haut, entrez-y un nombre $n$ et appuyer sur la touche «Entrée» : la valeur de $f(n)$ apparaît alors dans la case en-dessous).

Les différents jeux cachent des fonctions a priori différentes. Votre objectif est de décider si, oui ou non, ces fonctions satisfont certaines propriétés.

Est-elle nulle ?

Passons à un autre jeu. Le principe est le même, mais ici on vous demande de décider si la fonction cachée $f$ définie par extension est nulle, c’est-à-dire si pour chaque valeur de $n$, $f(n)=0$ (les fonctions $f,g,h$ ne sont pas a priori les mêmes que ci-dessus).

Premier(n)
Si n < 2 alors renvoyer 0,
Sinon
    d ← 2,
    Tant que d*d <= n faire :
        Si d divise n alors
            Renvoyer 0,
        Sinon d ← d+1.
    Renvoyer 1.

Nul(n).
Renvoyer 0.

Decomposable(m)
Si m = 4 alors renvoyer 1.
p ← 3.
Tant que 2*p <= m faire :
    Si Premier(p)=1 et Premier(m-p)=1 alors
        Renvoyer 1,
    Sinon p ← p+2.
Renvoyer 0.

Goldbach(n).
m ← 2*n+4.
Si Decomposable(m)=1 alors
    Renvoyer 0,
Sinon
    Renvoyer 1.

Quand l’algorithme en dit plus long

Résumons la section précédente : les résultats présentés tendent à montrer qu’on ne peut pas toujours obtenir plus d’information sur la fonction en lisant un algorithme plutôt qu’en l’exécutant. Ainsi, la seule manière systématique d’exploiter un algorithme quelconque semble être de l’exécuter.

Cependant, le logicien américain Richard M. Friedberg a montré en 1958 que dans certaines situations, avoir accès au contenu de l’algorithme fournit une information supplémentaire.

La preuve de Friedberg repose sur la construction d’une telle propriété. Nous présentons ici une autre propriété, proche de celle découverte par Friedberg, plus simple à présenter.

Compression

Si l’on imagine une fonction comme une table associant une valeur $f(n)$ à chaque entrée $n$, c’est un objet infini qui peut parfois être représenté par un objet fini, un algorithme. C’est comme si l’on avait compressé un fichier de taille infinie en un fichier habituel, de taille finie. Quel gain de place !

Apportons maintenant quelques nuances. La taille d’un algorithme est certes toujours finie, mais peut être extrêmement grande. Imaginons un algorithme de 10 000 lignes calculant une certaine fonction $f$. Si l’on est intéressé par les valeurs de cette fonction seulement sur les entiers allant de $0$ à $100$, un tel algorithme n’est pas une représentation efficace de ces valeurs de la fonction, et certainement pas une version compressée. Une table contenant explicitement les valeurs $f(0),f(1),\ldots,f(100)$ sera une représentation plus compacte (cependant ce n’est toujours pas une compression). En revanche si l’on a besoin de connaître les valeurs de $f$ sur les entrées allant de $0$ à $1\,000\,000$, cet algorithme sera bien une représentation compressée de la table $f(0),\ldots,f(1\,000\,000)$.

Bref, un algorithme donné n’est une compression de la fonction qu’à partir d’un certain rang. Cela nous amène assez naturellement à poser les définitions suivantes.

Etant donnée une suite finie, on peut découvrir si elle est compressible en essayant bêtement chaque algorithme de moins de $n$ caractères. En revanche, si la suite n’est pas compressible c’est une tâche bien plus difficile voire impossible de s’en apercevoir et de le démontrer.

Donnons quelques illustrations de cette notion.

La fonction nulle

La fonction nulle devient très rapidement compressible, à partir du rang 12. En effet, l’algorithme suivant calcule la fonction nulle et contient 11 caractères (Renvoyer 0.), donc fournit une représentation compressée de toute suite $0, 0, \dots, 0$ d’au moins 12 valeurs.

Nul(n)
Renvoyer 0.

La fonction de Goldbach

Considérons maintenant la fonction $G$ définie comme suit, et calculée par l’algorithme Golbach défini plus haut :
\[ G(n)=\begin{cases} 0&\text{si }2n+4\text{ est une somme de deux nombres premiers,}\\ 1&\text{sinon.} \end{cases} \]

La conjecture de Goldbach revient à dire que la fonction $G$ est nulle. Si c’est le cas alors comme nous venons de le dire, la fonction $G$ est compressible à partir du rang 12. Mais nous ne savons toujours pas si cette conjecture est vraie. Cependant, nous pouvons quand même affirmer que $G$, nulle ou pas, est compressible à partir du rang 12 ! Voici comment procéder.

Observons l’algorithme Goldbach calculant la fonction $G$ donné ci-dessus. L’algorithme complet contient un peu moins de 400 caractères. On peut donc immédiatement affirmer que la fonction $G$ est compressible à partir du rang 400.

Les vérifications au cas par cas montrent que $G$ est nulle pour toutes les entrées inférieures à $2\times10^{18}$ et en particulier inférieures à 400.
Ainsi, l’algorithme calculant la fonction nulle, de taille 12, est une meilleure représentation de la fonction $G$ jusqu’au rang 400. Pour chaque $n$ entre 12 et 400, l’algorithme Nul contient moins de $n$ caractères et produit la suite $G(0),\ldots,G(n)$, qui est donc compressible.

Ainsi, la meilleure représentation d’une même fonction peut varier selon la fenêtre dans laquelle nous regardons cette fonction.

Bref, même si l’on ne connaît pas la fonction $G$ dans son ensemble, on a quand même pu déterminer qu’elle est compressible à partir du rang 12.

Une fonction quelconque

Peut-on savoir si une fonction quelconque est compressible à partir du rang 12 [5] ? Oui et non !

Le deuxième point se démontre ainsi : on ne peut jamais être certain qu’une fonction est compressible à partir du rang 12 en ayant seulement accès à une table, car il faudrait parcourir l’intégralité de cette table infinie. En effet, la propriété «être compressible à partir du rang 12» dépend de toutes les valeurs de $f$, comme la propriété «être nulle».

Le premier point se démontre ainsi : si l’on dispose d’un algorithme calculant la fonction $f$, celui-ci nous donne une limite au-delà de laquelle il n’est pas nécessaire de consulter la table. Le principe est le même que pour la fonction $G$. L’algorithme dont on dispose est un texte d’une certaine longueur, disons $t$ caractères : on sait déjà que la fonction est compressible à partir du rang $t$.

• Si $t\leq 12$, l’algorithme supposé est de longueur inférieure à 12 et engendre chaque suite $f(0),\ldots,f(n)$ pour tout $n$ supérieur ou égal à 12 : c’est la définition de la compressibilité à partir du rang 12.

• Si $t>12$, le raisonnement précédent donne la compressibilité
  à partir du rang $t$, il suffit donc de prouver la compressibilité des
  suites
  \[ \begin{align*} &f(0),\ldots,f(12)\\ &f(0),\ldots,f(12),f(13)\\ &\ldots\\ &f(0),\ldots,f(12),f(13),\ldots,f(t) \end{align*} \]
  Ces suites sont en nombre fini et la compressibilité de chacune peut-être vérifiée. Si toutes sont compressibles, on sait que $f$ est compressible à partir du rang 12.

Notez que le raisonnement n’utilise que la taille de l’algorithme calculant la fonction (en fait il suffit de connaître un majorant quelconque).

C’est la taille qui compte

On a vu dans l’exemple précédent qu’avoir accès à un algorithme calculant une fonction pouvait donner plus d’information qu’avoir un accès direct à la fonction au moyen d’une table. Dans cet exemple, l’information supplémentaire était simplement la taille de l’algorithme. Existe-t-il d’autres exemples où un autre type d’information, caché dans le contenu de l’algorithme, pourrait être exploité ? La réponse est non : la taille de l’algorithme est la seule information supplémentaire exploitable.

Ainsi, un algorithme calculant une fonction :

• permet de retrouver les valeurs de cette fonction, en l’exécutant sur chaque entrée possible,
• nous renseigne sur la compressibilité de la fonction, à travers sa taille,

et ce sont en général les seules informations que l’on peut exploiter.

Pour conclure

Ces résultats sont intrigants car ils révèlent des subtilités dans le jeu entre le fini et l’infini, en explorant les limites qu’imposent des ressources de calcul finies sur la connaissance que l’on peut avoir d’objets infinis. Ils mettent en relation deux types de limitations a priori très différentes : que l’objet infini soit présenté sous forme finie (algorithme) ou infinie (table), un ordinateur ne peut en avoir qu’une connaissance partielle dans un temps limité :

• parce que parcourir une table prend du temps,
• parce qu’effectuer des calculs prend du temps.

Ces deux contraintes, l’une spatiale et l’autre temporelle, sont de natures très différentes et pourtant plusieurs résultats classiques (Théorèmes 1 et 2 ci-dessus et d’autres encore) montrent qu’elles ont le même effet. L’exemple de Friedberg montre cependant qu’elles ne sont pas entièrement équivalentes. Comprendre la différence est ce qui m’a poussé à effectuer ce travail de recherche. La réponse, donnée par le théorème 5, est très parlante : quoi sinon la taille différencie un objet fini d’un objet infini ?

Le lecteur expert pourra consulter l’article de recherche contenant ce dernier théorème, co-écrit par l’auteur.