Que calcule cet algorithme ?

Piste bleue Le 14 septembre 2015  - Ecrit par  Mathieu Hoyrup Voir les commentaires (2)

Lire un algorithme donne-t-il plus d’information sur ce qu’il calcule que de l’exécuter aveuglément ?

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$
Spirale d'Ulam
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

Pour comprendre l’algorithme ci-dessus

Si vous n’êtes pas familier avec la programmation, vous pouvez exécuter l’algorithme pas à pas pour comprendre comment cela fonctionne. Observez par exemple le déroulement de l’algorithme pour n=9 et n=29 (cliquez sur « Lancer » pour démarrer, puis sur « Poursuivre » pour exécuter l’algorithme pas à pas).

Entrée n=.
n vaut  ?
d vaut  ?
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.

C’est un exercice de licence de montrer que Premier(n) retourne 1
si et seulement si n est un nombre premier.

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-ce que $f(0)$ est pair ?
Oui Non

Réponse

$f(0)=0$ est pair.

Est-ce que $g(2)+g(3)=g(4)$ ?
Oui Non

Réponse

Plus généralement, $g(n)+g(n+1)=g(n+2)$ : c’est la suite de Fibonnacci.

Est-ce que $h(h(1))=24$ ?
Oui Non

Réponse

$h(1)=5$ et $h(5)=25$. Plus généralement, $h(n)=5\times n$.

On se rend vite compte que l’on peut toujours déterminer de manière sûre la réponse à ces questions, en consultant un nombre fini de valeurs de la fonction. Autrement dit dans chaque cas il y a une méthode systématique qui permet de donner à coup sûr la bonne réponse à ces questions. On dit qu’on peut décider si les propriétés « $f(0)$ est pair », etc. sont satisfaites, ou que ces propriétés sont décidables à partir de la table des valeurs de $f$. Nous allons voir par la suite que certaines propriétés ne sont pas décidables.

Voici donc une première façon de comparer l’information donnée dans
chacun des cas :

Quels types de propriétés peut-on décider de manière systématique à partir de la table des valeurs d’une fonction ? Et à partir d’un algorithme calculant cette fonction ?

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).

Est-ce la fonction nulle ?
Oui Non

Réponse

$f(n)$ teste si $n$ est un nombre premier.

Est-ce la fonction nulle ?
Oui Non

Réponse

C’est bien la fonction nulle partout.

Est-ce la fonction nulle ?
Oui Non

Réponse

$h(n)$ teste si $n$ est l’année de la bataille de Marignan.

On s’aperçoit rapidement que si l’on n’a accès qu’aux entrées de la table, on ne peut pas se prononcer tant que la fonction renvoie $0$. En particulier si la fonction est nulle partout, on ne pourra jamais en être certain. On dit qu’on ne peut pas décider si la fonction est nulle. Une dissymétrie apparaît ici :
  • Si la fonction est nulle, on n’en aura jamais la preuve en temps fini car il faudrait connaître une infinité de valeurs de $f$ pour le savoir.
  • Si la fonction n’est pas nulle, on finira par le savoir, en connaissant un nombre fini de valeurs de $f$.

On dit qu’on peut semi-décider que la fonction n’est pas nulle. En revanche on ne peut pas semi-décider que la fonction est nulle. La propriété « ne pas être nulle » est semi-décidable à partir de la table des valeurs de $f$, mais pas décidable.

Que se passe-t-il maintenant si la fonction vous est donnée sous forme d’algorithme ? Cette fois vous pourrez, avant même de commencer à jouer, lire entièrement l’algorithme : ainsi si vous arrivez à comprendre l’algorithme vous connaîtrez entièrement la fonction. Cela suffira-t-il ?

Encore une fois, nous réutilisons les noms $f,g,h$ pour désigner de nouvelles fonctions.

L’algorithme calcule-t-il la fonction nulle ?
Oui Non
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.

Réponse

L’algorithme teste si $n$ est un nombre premier.

L’algorithme calcule-t-il la fonction nulle ?
Oui Non
Nul(n).

Renvoyer 0.

Réponse

L’algorithme renvoie immédiatement $0$ quelle que soit l’entrée.

L’algorithme qui suit fait appel à un autre algorithme, Decomposable(m), qui teste si son entrée m est une somme de deux nombres premiers. Le lecteur curieux peut consulter cet autre algorithme ci-dessous (mais cela n’est pas nécessaire pour comprendre la suite).

L’algorithme Decomposable(m)

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.

Notez que cet algorithme fait lui-même appel à l’algorithme Premier(p) donné plus haut qui teste si p est un nombre premier.

L’algorithme calcule-t-il la fonction nulle ?
Oui Non
Goldbach(n).

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

Réponse

Aujourd’hui nul ne peut affirmer que cet algorithme calcule la fonction nulle. Cela est fortement soupçonné mais ce n’est pour l’instant qu’une conjecture, la conjecture de Goldbach, qui dit que tout nombre pair (hormis 2) est une somme de deux nombres premiers. La conjecture de Goldbach peut être facilement vérifiée au cas par cas : 4=2+2, 6=3+3, 8=3+5, 10=5+5, 12=5+7, 14=7+7, 16=5+11, etc.
Grâce au travail de Tomás Oliveira e Silva elle a d’ailleurs été vérifiée pour tous les entiers pairs inférieurs à
$4\times 10^{18}$ . Mais
si un seul échec aurait démontré sa fausseté, toutes ces réussites ne
montrent pas sa vérité !

Le texte de l’algorithme étant connu, il est parfois possible de décider si la fonction est nulle, lorsque l’algorithme renvoie clairement 0 sur chaque entrée, comme par exemple l’algorithme Nul(n) ci-dessus. Cependant, la compréhension de certains algorithmes peut se révéler aussi ardue que n’importe quelle question de mathématiques, y compris celles qui ne sont pas résolues à ce jour ! Ces exemples suggèrent qu’il n’y a pas de méthode systématique permettant de répondre à cette question pour chaque algorithme, de manière sûre et certaine, sauf à disposer d’une recette permettant de trancher des problèmes de recherche mathématique jusqu’ici non résolus. Inutile de dire qu’on n’en connaît pas !

C’est bien pire ! Un résultat fondamental de logique dû notamment au fameux Alan Turing montre que l’analyse des algorithmes est impossible en général : il n’y a pas de méthode systématique permettant de décider, ni même de semi-décider, si un algorithme quelconque calcule la fonction nulle. C’est-à-dire que l’on ne peut pas concevoir de programme informatique qui analyserait n’importe quel algorithme et finirait par déterminer si oui ou non l’algorithme calcule la fonction nulle. On peut imaginer des méthodes qui vont répondre correctement dans de nombreux cas (pour des algorithmes « simples »), mais il n’est pas possible de répondre correctement dans tous les cas.

Théorème 1 [Turing, 1936 [4] - Rice, 1953] : Il n’y a pas de manière systématique de décider, ni même semi-décider si une fonction est nulle, à partir d’un algorithme calculant la fonction.

Ainsi, dans certains cas, connaître un algorithme calculant la
fonction ne permet pas davantage d’établir sa nullité, qu’une table recensant les valeurs de cette fonction.

Cela n’est pas spécifique à la propriété « être nulle ». Il existe un résultat général montrant qu’on ne peut rien décider (systématiquement) de plus à partir d’un algorithme qu’à partir d’une table.

Théorème 2 [Kreisel-Lacombe-Shoenfield, 1957 - Ceitin, 1962] : Les propriétés décidables des fonctions sont les mêmes, que l’on puisse lire un algorithme calculant la fonction ou seulement l’exécuter.

Ces propriétés ont une forme particulière : la propriété peut être vérifiée en ne consultant la fonction que sur un nombre fini d’entrées. C’est par exemple le cas des toutes premières propriétés proposées ci-dessus. Ce n’est par exemple pas le cas de la propriété « être nulle », qui dépend de toutes les valeurs prises par la fonction.

Ce dernier résultat concerne les propriétés décidables. Qu’en est-il des propriétés semi-décidables ?

Peut-on semi-décider les mêmes propriétés à partir de la table des valeurs d’une fonction ou à partir d’un algorithme calculant cette fonction ?


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.

Théorème 3 [Friedberg, 1958] : Il existe une propriété des fonctions :
  • qui est semi-décidable lorsqu’on a accès à n’importe lequel des algorithmes calculant la fonction,
  • mais qui ne l’est pas lorsqu’on a seulement accès à une table des valeurs de la fonction.

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.

Définition 1 : Une suite finie de nombres $a_0,\ldots,a_n$ est compressible s’il existe un algorithme de moins de $n$ caractères qui calcule $a_0$ sur l’entrée $0$, $a_1$ sur l’entrée $1$, etc. et $a_n$ sur l’entrée $n$.

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.

Définition 2 : Soit $p$ un entier fixé. Une fonction $f$ est compressible à partir du rang $p$ si pour chaque $n\geq p$, la table $f(0),\ldots,f(n)$ est compressible.

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 !

Théorème 4 [adapté de Friedberg] : Savoir si une fonction $f$ est compressible à partir du rang 12 :
  • est semi-décidable si l’on dispose d’un algorithme calculant $f$,
  • n’est pas semi-décidable si l’on peut seulement consulter une table de $f$.

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.

Théorème 5 : Les propriétés semi-décidables sont les mêmes :
  • à partir d’un algorithme calculant la fonction,
  • à partir d’une table des valeurs de la fonction accompagnée de la taille [6] de l’algorithme.

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.

Post-scriptum :

L’auteur remercie les relecteurs Jean-Romain, Rafael, Clément Caubel, Lison, Jean Lefort et Jérôme Buzzi pour leur relecture attentive et leurs commentaires judicieux.

Article édité par Jérôme Buzzi

Notes

[1Vous trouverez d’autres manières de multiplier ici. Pour rappel, l’algorithme de multiplication classique donnerait dans notre cas :

     1 5 9
 x   4 2 3
-----------
     4¹7²7
   3¹1¹8
 6²3³6
-----------
 6 7¹2¹5 7

soit $159\times 423=67\,257$.

[2Allez voir ici pour en savoir plus sur les algorithmes

[3Rappelons qu’un nombre est premier s’il a exactement 2 diviseurs, $1$ et lui-même. La liste des nombres premiers commence ainsi : $2,3,5,7,11,13,17,19,23,29,31,37,\ldots$

[4À proprement parler, Turing a montré qu’on ne peut pas décider si l’exécution d’un algorithme quelconque s’arrête. Cependant, savoir si un algorithme A renvoie toujours $0$ revient à savoir si l’algorithme cherchant une valeur non nulle de A, ne s’arrête pas.

[5Le nombre 12 est arbitraire, toute la discussion reste valable si l’on remplaçait 12 par un nombre $p$ quelconque.

[6En réalité la taille exacte n’est pas importante, il suffit de disposer d’un majorant, c’est-à-dire de n’importe quel nombre plus grand que cette taille.

Partager cet article

Pour citer cet article :

Mathieu Hoyrup — «Que calcule cet algorithme ?» — Images des Mathématiques, CNRS, 2015

Crédits image :

Image à la une - Image fabriquée par l’auteur au moyen de Metapost et d’un programme Java.
« LA » table de multiplication. - Image fabriquée par l’auteur au moyen de Metapost et d’un programme Java.
Spirale d’Ulam - Image fabriquée par l’auteur au moyen d’un programme Java puis de Gimp pour créer le fichier GIF.

Commentaire sur l'article

  • Merci

    le 14 septembre 2015 à 14:53, par Samuel

    ... pour ce bel article rendu très accessible par son auteur.

    Répondre à ce message
  • Super !

    le 17 septembre 2015 à 11:56, par Lhooq

    Quel plaisir de voir une personne sachant vulgariser aussi bien !

    Merci beaucoup !

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM