Le problème des 12, 39, 120, ..., boules

Ce problème récréatif illustre la notion de bilan informationnel : on donne N boules, d'apparences identiques sauf que l'une d'entre elles est peut-être plus lourde ou plus légère que les autres. Combien de pesées sont nécessaires pour identifier l'intruse éventuelle ? On ne dispose que d'une balance à fléau, non graduée. Classiquement, on ne considère que le cas, N=12 qui se règle en k=3 pesées.

La théorie de l'information apporte une solution élégante au problème général. L'information manquante se calcule sur base du logarithme (en base 2) du nombre des solutions possibles, supposées équiprobables, soit, ℓg(2N+1) bits (Dans le cas, N=12, cela représente ℓg25 = 4.64386 bits).

L'apport informationnel d'une pesée dépend du nombre de boules que l'on dépose dans chaque plateau. Si on dépose x boules de chaque côté, les probabilités que le fléau penche à gauche, reste en équilibre ou penche à droite valent respectivement:

L'apport d'information se calcule sur base de la formule de Claude Shannon :

Cette fonction est maximum lorsque x=N/3 (soit x=4 dans l'exemple de 12 boules).

Cette pesée favorable apporte ℓg3 = 1.585 bits par pesée indépendante.

Vu que 3 x 1.585 = 4.75489 > 4.64386 (bits), rien ne semble s'opposer à ce qu'il existe une solution en k=3 pesées dans le cas N=12 (dont l'existence ne peut être établie qu'en la détaillant !).

La solution proposée par John Conway, l'un des mathématiciens les plus inventifs de sa génération, est particulièrement élégante. On détaille l'exemple classique k=3, N=12 mais la généralisation est immédiate, disponible en annexe (Notebook Mathematica).

Quel que soit k, Conway travaille sur un alphabet de 3 lettres, G, D et E, observant qu'il permet de former 3^k = 27 mots distincts de k=3 lettres. De cette liste, il enlève les mots constants, GGG, DDD et EEE, ne retenant que ceux où le premier changement de lettre respecte l'un des schémas GD DE ou EG. Au bilan il reste 12 mots distincts qu'il associe à chacune des 12 boules :

GGD GDG GDD GDE DDE DEG DED DEE EGG EGD EGE EEG

Les trois pesées mettent en balance les boules suivantes :

1:	GGD GDG GDD GDE	DDE DEG DED DEE
2:	GGD EGG EGD EGE	GDG GDD GDE DDE
3:	GDG DEG EGG EEG	GGD GDD DED EGD

où la i^ième pesée place les boules codées par G en i^ième position à gauche et celles codées par D en i^ième position à droite. Chaque pesée fournit un résultat que l'on note, G, si le fléau penche à gauche, D, s'il penche à droite et, E, s'il reste en équilibre. Les trois lettres, prises dans cet ordre, forment un mot. S'il fait partie de la liste des 12 mots retenus, il désigne la boule anormale et elle est plus lourde. S'il n'en fait pas partie, il suffit de transposer les lettres D et G pour désigner la boule anormale et elle est plus légère. Si le mot trouvé est EEE, toutes les boules sont identiques. GGG et DDD n'apparaissent jamais.

La méthode de Conway se généralise immédiatement à un nombre plus grand de pesées (et de boules !). La pesée la plus porteuse d'information place x = N/3 boules dans chaque plateau (à condition que N soit divisible par 3 !), amenant ℓg3 = 1.585 bits. On serait alors tenté de raisonner ainsi : k pesées indépendantes apportent k ℓg3 (bits) or il faut combler ℓg(2N+1) bits d'information manquante d'où k pesées devraient venir à bout du problème à N=(3^k-1)/2 boules. C'est un peu vite dit car ce N-là n'est pas multiple de 3 d'où l'information apportée par chaque mesure est inférieure au maximum escompté, 1.585 bits. En fait, (3^k-2)/2 n'est pas davantage multiple de 3, par contre N = (3^k-3)/2 l'est. C'est la solution optimale cherchée et la construction de Conway continue de s'appliquer.

En résumé, k pesées résolvent le problème des (3^k-3)/2 boules et inversement. En particulier, 2,3,4,5, …, pesées suffisent tout juste pour régler le problème comportant 3, 12, 39, 120, …, boules.

Quelques exemples de programmes en langage Fractran

John Conway est encore à l'honneur grâce à l'un de ces joyaux dont il a le secret : Fractran. Il a publié l'essentiel de son travail, en 1987, dans l'ouvrage collectif "Open Problems in Communication and Computation (Springer Verlag)". Ce résumé s'inspire de cette publication et de quelques essais isolés, parus dans des forums spécialisés.

Fractran est un langage un brin ésotérique mais universel au sens de Turing donc équivalent au modèle de la machine du même nom, qui incarne classiquement la notion de calcul. On sait que le kit minimal d'instructions nécessaires à la programmtion de n'importe quelle fonction calculable est ridiculement mince. On connait plusieurs modèles calculatoires formellement équivalents dont le plus simple est sans doute la machine à registres présentée par ailleurs sur ce site, à la rubrique Séminaires. Fractran est équivalent à la machine à registres grâce au fait que tout entier naturel possède une décomposition unique en facteurs premiers, les atomes de l'arithmétique. Ainsi l'entier, 600 = 2³3¹5² peut être vu comme l'encodage des entiers 3, 1 et 2 dans trois registres distincts. A partir de ces prémices, Conway a imaginé le langage suivant :

• Tout algorithme applique un programme à un ensemble de données. Un programme Fractran est représenté par une suite, F, ordonnée et finie, de fractions rationnelles. Les données sont représentées par un entier, n. L'algorithme fonctionne itérativement comme suit :
• L'entier n est multiplié successivement par les fractions de la suite F jusqu'à tomber sur un entier. Lorsque celui-ci est trouvé, il prend la place de n et le processus des multiplications successives recommence. Le calcul s'interrompt lorsqu'aucun produit n'est trouvé entier : l'entier en cours est alors imprimé. Le lecteur vérifiera, à la main, que les programmes suivants effectuent les tâches algorithmiques annoncées. Il peut aussi se référer aux programmes joints en annexe (Notebook Mathematica). Il notera qu'il est possible de proposer des progammes Fractran concis qui effectuent des tâches non triviales, une performance généralement interdite aux machines de Turing. Les plus curieux chercheront d'autres exemples mais la recherche des programmes, F, requiert une certaine expertise.

Une variante aisée du tour de Cheney

Attribué à William Fitch Cheney (1831-1879), ce tour de cartes refait régulièrement surface dans les magazines spécialisés. Jean-Paul Delahaye a fait une synthèse des variantes existantes dans une de ses chroniques mensuelles de la revue, Pour la Science (02/2006). Exempt de tout subterfuge, ce tour n'a rien de magique : il maximise le transfert d'information lors de l'échange d'un nombre donné de cartes discernables entre deux partenaires, dénommés Maurice, le magicien, et Alice, son assistante (Le tour fonctionne pareillement si Marie est la magicienne et Albert l'assistant). Quelle que soit la variante, le jeu traditionnel de 52 cartes est remplacé par un jeu de, N, cartes numérotées de 0 à N-1. Celle que nous proposons ici utilise N = n! + n cartes et elle présente l'intérêt de réduire l'intervention mathématique à sa plus simple expression.

Devinez l'entier !

Ce jeu un brin académique, entre deux partenaires nommés A et B, offre l'occasion de réfléchir à quelques concepts liés aux théories des probabilités et de l'information. Il se pose informellement de la manière suivante :

A sélectionne "au hasard" un entier positif, n, à charge pour B de le deviner le plus rapidement possible. Pour progresser dans sa recherche, B ne peut poser à A que des questions binaires de son choix, auxquelles A répond honnêtement, par oui ou par non.

Présenté en ces termes, le problème est mal posé car son énoncé est imprécis sur un point essentiel : il ne dit pas ce que signifie, pour A, la sélection d'un entier au hasard. On pourrait penser à la méthode suivante : A enferme des boules numérotées dans une urne, agite celle-ci consciencieusement et puise une boule donc un entier au hasard. Cette manière de faire n'est recevable que si le nombre des boules est fini, autrement dit si l'intervalle des entiers disponibles pour le tirage aléatoire est lui aussi fini, disons [1, N]. Encore faut-il préciser si l'urne contient exactement N boules numérotées chacune de 1 à N sans répétion ou si, au contraire, certains numéros sont présents plusieurs fois voire d'autres éventuellement absents (Dans la suite, on a remplacé l'urne et les boules par une cible circulaire et un jeu de fléchettes). On formalise ces exigences de la manière suivante : il faut que A renseigne B sur

• l'intervalle dans lequel il travaille, [1, N] s'il est fini, et [1, Infini], dans le cas contraire et de
• la densité distributionnelle, g(n), des probabilités qu'il utilise, favorisant éventuellement certains entiers par rapport à d'autres.

1. Le cas particulier suivant, classique et inoffensif, considère la densité homogène sur l'intervalle fini, [1, N] :
   

   

   

   
   L'information manquante vaut ℓg(N) bits (formule de Shannon), ce qui autorise à penser qu'une stratégie existe, pour B, lui permettant de deviner l'entier inconnu en Ceil[ℓg(N)] questions binaires. Cette stratégie porte le nom de dichotomie binaire; on la rappelle dans le cas, N=32=2⁵, où 5 questions devraient suffire. A chaque étape, on réduit l'intervalle possible [a, b] de moitié, en posant la question, n > (a+b-1)/2 ? Voyons cela sur l'exemple, n = 25 :
   
   • 1^ère question : n>16 ? Réponse : OUI = 1 (Il reste les entiers allant de 17 à 32)
   • 2^ème question : n>24 ? Réponse : OUI = 1 (Il reste les entiers allant de 25 à 32)
   • 3^ème question : n>28 ? Réponse : NON = 0 (Il reste les entiers allant de 25 à 28)
   • 4^ème question : n>26 ? Réponse : NON = 0 (Il reste les entiers 25 et 26)
   • 5^ème question : n=25 ? Réponse : OUI = 1 (n = 25, notez que 25 se note 11001 en binaire)
   
   L'exemple N=32 fonctionne particulièrement bien parce que 32 est une puissance de 2 donc l'information manquante est entière dans ce cas (elle vaut 5 bits). Lorsque N n'est pas une puissance de 2, la dichotomie binaire demeure la stratégie optimale avec la nuance suivante. Supposons N=17, l'information manquante vaut, à présent, ℓg(N)=4.08746 bits. La stratégie binaire précédente devine certainement l'entier, n, en 5 questions (Après tout, qui peut le plus peut le moins) mais elle fait mieux, en moyenne, soit en 71/17 = 4.17647 questions binaires, ce qui nous rapproche de la limite de Shannon. Il suffit, pour le voir, d'examiner tous les cas de figures et de se rendre compte que 4 questions suffisent dans 14 cas sur 17 tandis qu'il en faut 5 dans 3 cas sur 17 seulement.
2. Le cas infini est nettement plus délicat. Commençons par remarquer qu'il n'est plus possible, dans ce cas, de considérer que tous les entiers sont équiprobables : la fonction de distribution, g(n), ne serait pas normalisable à l'unité. Une procédure effective permettant à A de sélectionner au hasard un entier arbitrairement grand n'est envisageable que selon un hasard non uniforme qui pénalise les grands entiers. Plus formellement, la fonction de distribution doit être suffisamment décroissante, lorsque n s'éloigne à l'infini, afin de garantir la normalisation de g(n). Une décroissance selon la loi, g(n)=1/n, ne suffit pas car la série harmonique diverge, par contre, une décroissance selon la loi, g(n)=1/n², convient certainement. Etudions ce cas :
   

   

   

   
   L'information manquante vaut dans ce cas précis (formule de Shannon) :
   

   

   Il ne faudrait pas en conclure que 3 questions binaires devraient suffire à B pour découvrir l'entier inconnu, à tous coups, d'ailleurs cela n'aurait aucun sens : tous les entiers étant possibles sans restriction de taille, il ne faut pas espérer deviner tous les cas en un nombre fini de questions. Ce que la formule de Shannon laisse espérer, dans le cas infini, est différent, à savoir qu'il existe une stratégie qui, en moyenne, devine l'entier caché en approximativement 2.4 questions binaires. Autrement dit, il se fera certainement que 10 ou 20 questions s'avèrent nécessaires mais ces cas coûteux seront rares. Cette stratégie optimale moyenne existe effectivement et elle est à nouveau basée sur la dichotomie équitable que voici dans le détail.
   
   Dans la série infinie suivante, la partition la plus équitable se note :
   

   

   d'où la 1^ère question posée par B :
         n>1 ? Une réponse négative ne laisse la place qu'à une seule valeur pour n, soit n=1. Dans ce cas favorable, une seule question a suffi.
   
   Si la réponse à la première question est positive, il convient de poursuivre en partitionnant équitablement le reste de la série infinie. On trouve :
   

   

   d'où la 2^ème question posée par B :
         n>3 ? Une réponse négative ne laisse la place qu'aux deux valeurs, n=2 et n=3, d'où une question supplémentaire suffit pour trancher. Au bilan, dans ce cas favorable, 3 questions ont suffi sinon il convient de poursuivre la recherche avec la partition suivante :
   

   

   d'où la 3^ème question posée par B :
         n>7 ? Une réponse négative laisse la place aux quatre valeurs, n=4, n=5, n=6 et n=7, d'où deux questions supplémentaires suffisent pour trancher. Au bilan, dans ce cas favorable, 5 questions suffisent sinon il convient de poursuivre la recherche avec la partition suivante.
   
   Poursuivant la manoeuvre avec les restes successifs,
   on trouve que la k^ième question revêt la forme simple :
         n>2^k-1 ? Une réponse négative ne laisse la place qu'à 2^k-1 valeurs pour n, allant de n=2^k-1 à n=2^k-1, inclus, d'où k-1 questions supplémentaires suffisent pour trancher; au bilan, cela fait 2k-1 questions dans ce cas favorable.
   
   Note : cette affirmation repose sur la double inégalité remarquable, donnée sans démonstration :
   

   

   Au bilan, le nombre moyen de questions binaires que B doit poser se calcule comme suit :
   

   

   Il n'y a pas lieu de s'étonner que ce nombre soit légèrement supérieur à la valeur théorique de Shannon (2.36529) : les partitions opérées successivement ne sont qu'approximativement égales et cela a un prix bien connu en théorie de l'information.
   
   On le voit, la meilleure stratégie, sans être particulièrement imaginative, est plutôt efficace puisqu'elle règle le problème en 2.45 questions, en moyenne. Cette belle performance résulte du fait qu'on a utilisé une stratégie tenant compte de la décroissance de, g(n), qui oblige A à choisir plus fréquemment des entiers de petite taille. Notez que la stratégie naïve consistant à poser comme k^ième question, "L'entier cherché vaut-il k ?" est loin d'être optimale, le temps moyen devenant infini : c'est la conséquence de la divergence de la série harmonique.
3. Posons à présent que A veuille compliquer la tâche de B au maximum : il y parvient en utilisant une distribution, g(n), dont la normalisation repose sur une série convergeant vers 1 le plus lentement possible. Il est remarquable qu'une telle distribution - dite universelle - existe, qui se situe à la limite de la convergence et de la divergence. Elle est basée sur une suite de résultats analytiques concernant les séries infinies, que l'on rappelle :
   
   
   • Les séries infinies suivantes divergent toutes mais de plus en plus lentement :
     

     

     Par contre, les séries infinies suivantes convergent toutes mais de plus en plus lentement :
     

     

   • On en déduit que la série infinie suivante se situe à la frontière qui sépare la convergence de la divergence :
     

     

   
   Voyons le rapport que cette série entretient avec le tirage aléatoire d'un entier non borné. Commençons par noter que ce tirage ne peut reposer sur le principe naïf suivant : tout entier positif possédant une traduction binaire en termes de 0 et de 1, on lancerait une pièce de monnaie et la suite des tirages successifs pile (=1) ou face (=0) construirait (de droite à gauche) l'entier désiré. Cette procédure ne fonctionne pas pour la raison évidente qu'elle ne comporte aucune instruction d'arrêt : après avoir tiré, disons 10011, comment savoir s'il faut s'arrêter et accepter l'entier correspondant (19) ou continuer à lancer la pièce? Préfixer l'écriture binaire de 10011 par une étiquette binaire, 100, qui annoncerait la longueur (4) de sa partie significative (le 1 initial ne l'est pas) ne convient pas davantage car rien dans la succession des chiffres tirés, 100 00011, ne distinguerait la fin de l'étiquette du début du nombre proprement dit. La solution à ce case-tête est l'étiquetage répétitif : on préfixe bien la représentation binaire (amputée de son 1 initial non significatif) de n=10011 par une étiquette, 100, qui annonce la longueur (4) puis on fait de même avec une deuxième étiquette, 10, qui annonce la longueur (2) de la partie significative de la première et ainsi de suite jusqu'à tomber sur une étiquette de longueur 2 (=10) ou 3 (=11), ce qui ne peut manquer de se produire (Cette dernière étiquette ne peut être amputée de son 1 initial pour des raisons évidentes de décodabilité). On termine la procédure en préfixant le tout par autant de 0 que le nombre total d'étiquettes consommées, ce qui donnerait dans notre exemple, 00 10 00 0011, où les espaces servent seulement à faciliter votre lecture. Au bilan, le code préfixe de l'entier n=19 se note 00 10 00 0011 (Le décodage inverse est facile : ne pas oublier de rajouter les 1 initiaux à chaque étape). La procédure peut paraître coûteuse aux petites valeurs de n mais, asymptotiquement, on verra qu'il n'y a pas moyen de faire mieux. On trouvera, en annexe, le détail des procédures décrites (Notebook Mathematica).
   
   Le lecteur vérifiera, sur quelques valeurs de n, que la procédure fonctionne sur tous les entiers supérieurs à 3. Les entiers 1, 2 et 3 sont encodés séparément en commençant par un 1, ce qui empêche toute confusion. Au bilan, on trouve la liste suivante des codes préfixes universels des entiers positifs :
   
   S_pref = {
   
   s₁ ≡ 10, s₂ ≡ 110, s₃ ≡ 111, s₄ ≡ 01000, s₅ ≡ 01001, s₆ ≡ 01010, s₇ ≡ 01011,
   
   s₈ ≡ 011000, s₉ ≡ 011001, s₁₀ ≡ 011010, s₁₁ ≡ 011011, s₁₂ ≡ 011100, s₁₃ ≡ 011101, s₁₄ ≡ 011110, s₁₅ ≡ 011111,
   
   s₁₆ ≡ 0010000000, s₁₇ ≡ 0010000001,..., s₃₁ ≡ 0010001111,
   
   s₃₂ ≡ 00100100000, ..., s₆₃ ≡ 00100111111,
   
   ... }
   
   La suite, S, est affichée de telle façon que sa structure numérique devienne apparente : elle contient 1 code de longueur 2, 2 codes de longueur 3, 4 codes de longueur 5 et plus généralement 2^k codes de longueur ℓ(k), où la suite ℓ(k), croît comme (k = 0, 1, 2, 3, ...) :
   
   ℓ(k) = { 2, 3, 5, 6, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, …}.
   
   La suite, S, possède trois propriétés remarquables et essentielles pour le but poursuivi :
   

   

   • Les longueurs de codes, ℓ(k), croissent asymptotiquement comme : ℓ(k) = k + ℓg(k) + ℓg(ℓg(k)) + ℓg(ℓg(ℓg(k))) + ... . C'est la conséquence naturelle du fait que chaque étiquette allonge le code de n d'une valeur égale au logarithme de l'étiquette précédente, la première étiquette l'allongeant du logarithme de n.
   • La suite S est préfixe, ce qui signifie qu'aucun code d'entier n'est préfixe d'un autre code. C'est cette propriété qui justifie l'arrêt des tirages aléatoires dès qu'un terme de la suite est rencontré; il ne servirait, en effet, à rien de poursuivre.
   • La suite S est complète, ce qui signifie que tout tirage aléatoire est assuré de se terminer sur un code faisant partie de la suite.

On montre, en théorie de l'information qu'un code préfixe et complet satisfait l'égalité de Kraft :

On peut vérifier directement ce résultat en regroupant astucieusement les termes de cette série, de n=2^k à n=2^{2^k} -1 : les probabilités cumulées valent exactement 2^-k, livrant une progression géométrique de raison, 1/2, convergent vers 1.

La stratégie optimale que B doit suivre se dégage à présent sur base d'une dichotomie binaire :

• 1^ère question : n>3 ? Une réponse négative laisse la place aux trois valeurs, n=1, n=2 et n=3, d'où deux questions supplémentaires suffisent certainement pour trancher. Au bilan, dans ce cas favorable, 1+2=3 questions suffisent sinon (n>3) il convient de poursuivre la recherche avec la partition suivante.
• 2^ème question : n>15 ? Une réponse négative laisse la place aux douze valeurs, de n=4 à n=15, d'où quatre questions supplémentaires suffisent certainement pour trancher. Au bilan, dans ce cas favorable, 2+4=6 questions suffisent sinon (n>15) il convient de poursuivre la recherche avec la partition suivante.
• 3^ème question : n>65535 ? Une réponse négative laisse la place aux 65520 valeurs, de n=16 à n=65535, d'où seize questions supplémentaires suffisent certainement pour trancher. Au bilan, dans ce cas favorable, 3+16=19 questions suffisent sinon il convient de poursuivre la recherche avec la partition suivante.

Poursuivant la manoeuvre avec les restes successifs, on trouve que la k^ième question revêt la forme simple :

• k^ème question : n>2^2^..._{k symboles ^}^2 - 1 ? Une réponse négative "ne laisse la place qu'aux" valeurs de n, allant de n = 2^2^..._{(k-1) symboles ^}^2 à n = 2^2^..._{k symboles ^}^2-1, inclus, d'où 2^2^..._{(k-1) symboles ^}^2 questions suffisent (!) pour trancher. Au bilan dans ce cas "favorable", k + 2^2^..._{(k-1) symboles ^}^2 questions "suffisent" à ce stade.

Vu que 2^{-ℓ(code[n])} vaut précisément la probabilité de tirer au sort le code de n, on voit que l'égalité de Kraft remplit la condition de normalisation pour la densité de probabilité, g(n)=2^{-ℓ(code[n])}.

En adoptant cette distribution, A est assuré de compliquer au maximum la tâche de B précisément parce que c'est la distribution la plus lentement décroissante parmi toutes celles qui sont envisageables. Le fait que la conditon de normalisation se situe à l'extrême limite de la convergence a une conséquence dramatique pour B : le nombre moyen de questions binaires tend vers l'infini. Autrement dit, B ne peut accepter aucun pari proposé par A sans être assuré de se ruiner, à terme.

Une dernière remarque : lorsque B n'est pas informé de la loi, g(n), adoptée par A, il est contraint de faire comme si c'était la distribution universelle. Procéder autrement équivaudrait à introduire un élément d'information parasite de nature à privilégier abusivement les petits entiers. La seule attitude prudente, qui ne présuppose rien d'inconnu, consiste à adopter la loi g(n) la moins porteuse d'information, celle qui décroît asymptotiquement le plus lentement possible sans compromettre la normalisation. Cette loi c'est la distribution universelle ou toute autre distribution asymptotiquement équivalente.

Fonctions de Walsh et compression avec perte

Autant l'analyse de Fourier (discrète) des signaux (digitaux) est connue autant celle de Walsh l'est peu. Le principe de base est similaire : il s'agit de trouver un ensemble orthogonal complet de fonctions permettant de développer n'importe quelle suite (digitale), de longueur 2^s (s entier positif), en séries des fonctions de base. Alors que l'analyse de Fourier recourt à des fonctions de base trigonométriques, héritées de l'analyse infinitésimale, l'analyse de Walsh respecte le créneau binaire : ses fonctions de base ne prennent que deux valeurs, usuellement -1 et +1, pour des raisons de symétrie.

Il y a mille façons d'introduire les fonctions de Walsh mais l'approche récursive de Hadamard semble la plus simple. On commence par définir la suite des matrices de Hadamard 2^sx2^s, pour s = 0, 1, 2, …, comme suit :

Voici deux matrices de Hadamard, de tailles raisonnables (respectivement s=3 et s=4) :

Pour une valeur donnée de s, les fonctions de Walsh sont définies par les vecteurs lignes (ou colonnes car les matrices de Hadamard sont symétriques) de H_s. Voici les graphes de ces fonctions de Walsh dans les deux cas pris en exemple :

La méthode de Hadamard énumère les 2^s fonctions de Walsh, W_s,i (i = 1, 2, ..., 2^s), dans un ordre qui n'est pas nécessairement celui qui prévaut dans d'autres approches mais, au bilan, elles sont toutes bien présentes. Toutes sont orthogonales, au sens du produit scalaire habituel, et le carré de leur norme vaut 2^s. Autrement dit, les fonctions, 2^-s/2W_s,i forment un ensemble orthogonormé qui est de plus complet : toute fonction, V, étagée sur l'ensemble {-1, +1}, par exemple la fonction {1,1,1,1,1,1,-1,-1} (s=3), est décomposable en termes de fonctions de Walsh, W_3,i, et les coefficients du développement sont donnés par les produits scalaires, V.W_3,i. Cela résulte de l'identité :

(2^-s/2H_s.V)^T.(2^-s/2H_s) = V

Les fonctions de Walsh ainsi définies sont unidimensionnelles. Toute fonction de deux variables, étagée sur l'ensemble {-1, +1}, peut être développée en produits de fonctions de Walsh, 2^-sW_s,iW_s,j (i,j = 1, 2, ..., 2^s). Un exemple particulièrement intéressant est celui d'une image pixélisée sur une trame 2^sx2^s.

Statistique de la production des machines de Turing binaires simples (MTS)

Il existe beaucoup de présentations équivalentes des machines de Turing (MT) et nous optons pour le formalisme le plus compact, sans instruction explicite d'arrêt, dû à Stephen Wolfram et exposé dans son ouvrage, A New Kind of Science, en abrégé, NKS. Tous les calculs présentés en annexe (Notebook Mathematica) ont été programmés en langage Mathematica en respectant, à peu de choses près, l'ensemble des conventions fixées par Wolfram (sauf que celui-ci numérote bizarrement les états des MT de 1 à s alors que le faire de 0 à s-1 s'avère nettement plus simple; de même il code le déplacement de la tête des MT par -1 ou +1 selon qu'il s'effectue vers la gauche ou vers la droite mais il apparaît clairement à l'usage que les choix 0 et 1 sont préférables).

Une MTS se décrit en fonction de son nombre d'états, s, et de son nombre de caractères, k. On ne limite pas le pouvoir calculatoire des MTS en les restreignant à k=2 caractères, 0 et 1. Dans cette présentation, les MTS sont binaires et elles se décrivent comme suit :

• Une bande, semi-infinie, disons vers la gauche, partitionnée en cellules hébergeant un caractère binaire, 0 (cellule blanche) ou 1 (cellule noire).
• Une tête de lecture-écriture qui se déplace le long de cette bande, une cellule à la fois. Elle se trouve, à tout instant, dans un état, σ, parmi les s états autorisés (σ = 0, 1, ..., s-1), s pouvant prendre n'importe quelle valeur positive, s = 2, 3, 4, ... . La tête est initialement positionnée à l'extrémité droite de la bande, en face de la cellule n=0, et elle se trouve dans l'état σ = 0. Dans les figures qui suivent, l'état, σ, est représenté par l'aiguille d'une horloge qui pointe vers 12σ/s heures.
• Une table d'instructions qui dicte le comportement de la tête à chaque pas discret d'évolution. Ces instructions sont du type, {état actuel, caractère lu} → {nouvel état, caractère écrit, déplacement de la tête}. La machine évolue en respectant cette table : à chaque pas d'évolution, la tête lit le caractère situé en face d'elle et en fonction de l'état interne, elle le remplace par l'un des caractères possibles (éventuellement celui qui a été lu), elle change éventuellement d'état interne et elle se déplace (obligatoirement) d'une cellule vers la gauche (δ=0) ou vers la droite (δ=1). La machine ne s'arrête que lorsque la tête est invitée à dépasser l'extrémité fixe de la bande. Lorsque l'arrêt se produit, la réponse est lue de gauche à droite (la convention inverse serait tout aussi valable), entre la position la plus extrême-gauche atteinte par la tête et l'extrémité fixe.

L'absence d'instruction explicite d'arrêt garantit la concision maximale du formalisme. Certains auteurs incorporent une voire plusieurs instructions d'arrêt à la table d'instructions mais cela est inutile et même carrément redondant (On ne voit, en particulier, pas l'intérêt d'introduire une deuxième instruction d'arrêt lorsque la première a déjà été activée).

Une table comprend 2s instructions. Wolfram les range dans l'ordre immuable suivant (l'instruction en couleur est celle qui est activée en premier lieu) :

(0,1) → (σ1,κ1,δ1)	(0,0) → (σ2,κ2,δ2)
(1,1) → (σ3,κ3,δ3)	(1,0) → (σ4,κ4,δ4)
(2,1) → (σ5,κ5,δ5)	(2,0) → (σ6,κ6,δ6)
...	...
(s-1,1) → (σ2s-1,κ2s-1,δ2s-1)	(s-1,0) → (σ2s,κ2s,d2s)

La numérotation des MT s'effectue comme suit. Chaque triplet, (σ_j,κ_j,δ_j) définit un chiffre en base 4s, conformément au schéma :

(0, 0, 0) → 0	(0, 0, 1) → 1	(0, 1, 0) → 2	(0, 1, 1) → 3
(1, 0, 0) → 4	(1, 0, 1) → 5	(1, 1, 0) → 6	(1, 1, 1) → 7
...	...	...	...
(s-1, 0, 0) → 4s-4	(s-1, 0, 1) → 4s-3	(s-1, 1, 0) → 4s-2	(s-1, 1, 1) → 4s-1

La suite des triplets de la table, (σ₁,κ₁,δ₁)(σ₂,κ₂,δ₂) ... (σ_2s,κ_2s,δ_2s), définit donc un entier en base 4s qui numérote la machine de Turing sans ambiguïté. Par exemple, la machine binaire à 3 états, d'instructions, (0,1) → (1,0,1), (0,0) → (2,0,0), (1,1) → (0,1,0), (1,0) → (2,0,1), (2,1) → (0,0,0), (2,0) → (1,1,1), porte, en base 4s=12, le numéro 582907, qui résulte du calcul suivant : 5 12⁵+8 12⁴+2 12³+9 12²+0 12+7 = 1414807, en base 10.

Il existe (4s)^2s machines binaires distinctes à s états, soit respectivement, 4096 (s = 2), 2985984 (s = 3), 4294967296 (s = 4), 10240000000000 (s = 5), etc. Avec les conventions adoptées, elles sont numérotées de 0 à 4095, de 0 à 2985983, etc. Ci-contre évoluent trois machines à deux états, choisies parmi les 4096 existantes.

Bien que l'évolution d'une MT se situe entièrement sur la bande unidimensionnelle, une représentation bidimensionnelle qui archive tous les pas de l'évolution s'avère particulièrement parlante.

On remarque que la MT 2867 s'arrête après 7 pas (elle imprime la suite 101), tandis que les MT 2827 et 3477 ne s'arrêtent "visiblement" pas, l'une bouclant et l'autre divergeant. Les esprits chagrins pourraient exiger une démonstration de cette absence d'arrêt, ce qui ne peut se faire que dans un cadre axiomatique adéquat, par exemple celui de l'arithmétique de Peano. Une démonstration par récurrence est effectivement possible tant que s<5.

Les choses se compliquent éventuellement à partir de s = 5 car l'inspection visuelle devient problématique (10240 milliards de machines à prendre en considération) ! Concrètement, la tête de quelques dizaines de machines adopte un comportement erratique impossible à cerner aussi loin que pousse le temp de calcul. Il est, de fait, bien connu que l'arrêt des MT est frappé d'indécidabilité générique sans qu'on puisse connaître le seuil à partir duquel elle se manifeste.

Il est illusoire de croire que l'on pourrait démontrer l'arrêt de chaque machine individuellement en travaillant dans Peano car cette arithmétique est indécidable, au sens de Gödel cette fois, ce qui signifie qu'il existe une infinité de propositions bien formulées (dont l'arrêt des MT) qui ne sont ni démontrables ni réfutables dans ce cadre arithmétique (et pas davantage dans des cadres plus étendus, de la théorie des ensembles par exemple). Personne ne sait aujourd'hui avec certitude si les machines qui posent déjà problèmes dans le cas s=5 s'arrêtent ou ne s'arrêtent pas.

L'ensemble infini mais dénombrable des MT possédant un nombre quelconque, s, d'états et travaillant sur une bande semi infinie, initialement peuplée de 0 (ou de 1) est calculatoirement universel en ce sens qu'il est susceptible d'imprimer n'importe quelle suite finie au terme de son calcul. Toutes les suites ne sont cependant pas imprimées avec des fréquences égales : les suites moins complexes (dans un sens qui reste à préciser, cfr rubrique 7) sont exponentiellement plus souvent imprimées que les autres, conformément au principe d'Ockham. Le calcul des fréquences d'apparition des suites est accessible à un PC banal dans les cas s = 2 et s = 3 et avec un peu de patience, dans le cas s = 4. Ce travail a été envisagé pour la première fois par Hector Zenil dans le cadre de sa thèse de doctorat, effectué sous la direction de Jean-Paul Delahaye, à l'Université de Lille. Notre approche est légèrement différente, qui privilégie la compacité maximale de l'énumération des machines de Turing. En particulier, elle ignore les instructions d'arrêt, surnuméraires dans la présentation de Zenil, avec la crainte qu'une même machine soit comptabilisée plus d'une fois, d'où une statistique faussée. Nos résultats diffèrent d'ailleurs légèrement à cause de cela.

Compression sémantique des suites binaires courtes par MTS (Attention la numérotation des MTS diffère légèrement de celle au point 6 !)

Aucun algorithme ne peut prétendre compresser sans pertes toutes les suites (binaires ou autres) : compresser une suite binaire, c'est la remplacer sans ambiguïté par une suite plus courte qu'elle. Si on code une suite longue par une suite courte, que va-t-on faire de celle-ci sinon la remplacer par une suite plus longue qu'elle ? Autrement dit, un algorithme ne peut prétendre compresser sans pertes certaines suites qu'à la condition d'en dilater d'autres. Dès lors pourquoi s'intéresser à la compression ? La réponse tient en une ligne : toutes les suites ne se valent pas. Quel que soit le domaine d'activité, scientifique mais aussi littéraire ou musical, les suites aléatoires (de chiffres, de lettres ou de notes) n'intéressent pas grand monde et ce sont elles qui sont sacrifiées sur l'autel de la compression. Vu que les suites aléatoires sont incomparablement plus nombreuses, on parvient à ce compromis acceptable qu'une bonne méthode de compression est efficace sur les suites structurées au détriment des suites aléatoires qui sont légèrement dilatées.

La science peut être vue comme l'art de compresser les données numériques accumulées à la faveur d'observations. Mais de quelle compression veut-on parler : syntaxique (Shannon) ou sémantique (Kolmogorov) ? La suite des positions de la planète Mars dans le ciel, repérées à intervalles temporels réguliers, est certainement compressible au sens de Shannon car ces positions varient peu d'un jour à l'autre, d'où une répétition probable des premiers chiffres significatifs, signe d'une redondance syntaxique. Cependant cette compression, entièrement automatisable jusqu'à la limite de Shannon par des procédures connues, est encore très éloignée de la limite sémantique de Kolmogorov. Les physiciens présument que l'encodage de la résolution des lois de Newton sur un jeu de conditions initiales bien choisies approche sinon rejoint la limite sémantique de la description par programme des systèmes planétaires. Autrement dit, les lois de la nature compressent (sémantiquement) au mieux les données issues de l'observation. Le lecteur totalement néophyte en théorie de l'information peut souhaiter se reporter aux exposés préliminaires, disponibles sur ce site.

L'ensemble des suites binaires finies est récursivement énumérable dans l'ordre naturel :

L'entier qui caractérise une suite ne contient ni plus ni moins d'information que cette suite, d'ailleurs son écriture binaire est identique sauf l'absence du chiffre 1 initial, non significatif chez les entiers binaires positifs. Toute procédure visant à compresser les suites revient à réécrire les suites binaires dans un autre ordre, ce qui a effectivement pour résultat d'en compresser certaines et d'en dilater d'autres. Il y a, a priori, une infinité de façons de réordonner les suites mais celle qui nous intéresse doit privilégier les suites structurées par un programme court au détriment des suites aléatoires. Qui dit programme, dit machine de Turing, d'où l'idée de baser la compression scientifique sur l'aptitude des machines de Turing à produire les suites sur base du plus petit nombre d'instructions.

La complexité, K, d'une suite, S, est traditionnellement définie comme la longueur du plus court programme préfixe binaire alimentant une machine de Turing universelle (MTU) donnée, qui en provoque l'arrêt et imprime S. Ce programme minimum représente la meilleure compression (sémantique) de la suite imprimée. Formellement cela pourrait s'écrire :

Pour exploiter cette définition, il faudrait au moins se mettre d'accord sur une MTU, par exemple celle que Minsky a conçue dans les années 1960. Cependant les choses ne sont pas si simples car la MTU doit être (libre de tout) préfixe, autrement dit, les programmes qui l'alimentent doivent être auto-délimités (= uniquement décodables). Cela implique que toutes les suites binaires ne constituent pas un programme valable pour une MTU préfixe. Or s'il n'est pas difficile de proposer un codage préfixe complet des suites binaires, il est beaucoup plus délicat de démontrer que la MTU (par exemple celle de Minsky) demeure universelle pour ce choix restreint de suites-programmes.

Il est beaucoup plus simple de revenir vers les machines de Turing simples (MTS par opposition à MTU), alimentées initialement par une bande "vierge" : elles sont également collectivement universelles, à condition de n'en oublier aucune. Le modèle de ces MTS a été rappelé à la rubrique 6 ci-dessus, toutefois nous souhaitons y apporter quelques retouches. Les conventions adoptées par Wolfram sont malheureuses au niveau de l'ordre utilisé pour les énumérer, qui voit les états monter quand les caractères descendent. Il est plus judicieux que les états descendent comme les caractères : on a alors la certitude que les premières MTS à (s+1) états, reproduisent les comportements des machines à s états. Autrement dit, si on décide de se pencher sur l'étude des MTS à moins de 5 états, il n'est pas nécessaire de se préocupper des machines à 2 ou 3 états, celles-ci sont automatiquement reprises au début de l'étude des machines à 4 états. Voici l'ordre modifié dans la table d'instructions des MTS :

(s-1,1) → (σ1,κ1,δ1)	(s-1,0) → (σ2,κ2,δ2)
(s-2,1) → (σ3,κ3,δ3)	(s-2,0) → (σ4,κ4,δ4)
...	...
(1,1) → (σ2s-3,κ2s-3,δ2s-3)	(1,0) → (σ2s-2,κ2s-2,δ2s-2)
(0,1) → (σ2s-1,κ2s-1,δ2s-1)	(0,0) → (σ2s,κ2s,δ2s)

La compression des suites binaires par MTS à, disons 4 états, repose sur le principe suivant : on fait tourner toutes les MTS binaires à 4 états en ne retenant que celles qui s'arrêtent en imprimant une suite encore jamais imprimée. Lorsqu'une nouvelle suite apparaît, on symétrise le résultat en lui associant les suites inverse (lue à l'envers), conjuguée (0 et 1 permutés) et inverse de la conjuguée. On range ainsi les suites binaires dans un ordre différent de l'ordre naturel, qu'on pourrait appeler le schéma de compression MTS4 : la complexité algorithmique d'une suite vaut alors le nombre de chiffres significatifs de la représentation binaire de la place qu'elle occupe dans cette nouvelle numérotation et sa profondeur logique vaut (P+1)/2 où P est le nombre (toujours impair) de pas d'évolution de cette MTS minimale.

La figure ci-contre détaille l'évolution de la MTS binaire à 4 états portant le numéro 51088454. Elle est la première à imprimer la suite 111111111. La place qu'elle occupe dans l'inventaire des MTS compressantes porte le numéro 83, qui se note 1010011₂ en binaire. La suite 010011 (le 1 initial n'est jamais significatif chez les entiers binaires positifs) compresse donc la suite 111111111 avec un gain de 3 bits. La complexité algorithmique de la suite 111111111 vaut donc 6 bits et sa profondeur logique vaut la demi hauteur de la table d'évolution de ce programme minimum, soit 19. Mentionnons en passant que la profondeur logique d'une suite, S, de longeur n bits, est toujours supérieure ou égale à n : lorsqu'elle vaut précisément n, le programme minimum n'effectue aucun calcul intelligent : il se contente de construire la suite et de l'imprimer telle quelle en suivant un mouvement de simple aller-retour de la tête. Un tel programme s'appelle une imprimante et on a, en particulier, que le meilleur programme compresseur de toute suite réputée aléatoire ne peut être qu'une imprimante.

Nous sommes à présent en mesure de construire la table des compressions sémantiques des suites par MTS à 4 états. Tous les calculs sont présentés en annexe (Notebook Mathematica). On considère l'évolution des 4294967296 MTS à 4 états (numérotées de 0 à 4294967295) et on note la suite imprimée par la première machine qui s'arrête. C'est la MTS 1 (la MTS 0 diverge vers moins l'infini) : elle imprime la suite 0, à laquelle on attribue le numéro 2 (On convient d'attribuer le n°1 à la suite vide, c'est un détail sans importance). Sa conjuguée, 1, porte donc le n° 3. La MTS suivante qui s'arrête en imprimant autre chose que 0 et 1, déjà comptabilisés, est la MT 278; elle imprime 00 à laquelle on attribue le n° 4. Sa conjuguée, 11, porte donc le n° 5. Poursuivant l'investigation, on trouve que la MT 310 s'arrête en imprimant la suite, 01; on lui attribue le n° 6 donc le n°7 à son inverse (ou sa conjuguée) 10. Plus loin, on trouve, en 38^ème position, la MTS 1483700 qui imprime 110101 : celle-ci porte donc le n° 38 d'où 101011 porte le n° 39, 001010 le n° 40 et 010100 le n° 41 (l'ordre n'a pas vraiment d'importance dans cette classe d'équivalence et d'ailleurs le programme Mathematica, fourni en annexe, les classe plutôt dans l'ordre lexicographique).

Les calculs menés dans le cas, s=4, répertorient 588 MTS intéressantes, numérotées de 2 à 589. Voici, pour commencer, le tableau du nombre des suites de longueur 1 à 18, imprimées par les MTS à 4 états :

On constate que toutes les suites de longueur inférieure ou égale à 7 sont imprimées dans un ordre à peine bouleversé : seules quelques suites particulièrement régulières viennent s'intercaler entre des suites plus courtes et plus irrégulières.

Si l'on se concentre sur les premières suites imprimées, on constate que les suites de longueurs 1, 2 et 3 bits ne sont ni compressées ni dilatées : elles exigent toujours 1, 2 et 3 bits respectivement. Au sens de Kolmogorov elles peuvent être considérées comme aléatoires ce qui n'a rien de choquant puisqu'on s'attend effectivement à ce qu'un tirage à pile ou face les fasse apparaître fréquemment.

Les choses changent à partir des (16) suites de longueur 4 : 12 d'entre elles exigent encore 4 bits mais 0110, 1001, 0011 et 1100 en exigent 5. Cette dilatation de 1 bit est compensée par la compression de 1 bit de quatre suites de longueurs 5 (01010, 10101, 00000 et 11111). Sans surprise, ce sont des suites particulièrement régulières qui ont été compressées.

Ce phénomène s'amplifie lorsqu'on considère les suites plus longues.

Voici la fin de ce tableau où des suites régulières longues s'intercalent parmi des suites irrégulières plus courtes :

Cette compression par MTS à 4 états n'est qu'une étape d'un processus plus général qui, en théorie, doit être étendu à un nombre croissant d'états. On verrait alors progressivement apparaître les suites actuellement absente de l'inventaire. Une double difficulté surgit à ce stade :

• le temps de calcul explose rapidement, non seulement parce que le nombre des MTS croît rapidement (Il existe (4s)^2s MTS binaires à s états, soit respectivement, 4096 (s = 2), 2985984 (s = 3), 4294967296 (s = 4), 10240000000000 (s = 5), ... )
• et surtout, dès que s=5, certaines machines tournent sans faire mine de s'arrêter ni de boucler. On sait que tôt ou tard, on se heurtera au problème générique de l'indécidabilité de l'arrêt des MTS et à sa conséquence naturelle, la non calculabilité de la complexité algorithmique des suites. Nul ne sait à ce jour si les MTS à 5 états sont effectivement concernées par ce problème. Les seuls résultats acquis sont les suivants : les MTS à 2 états (resp. 3 et 4 états) qui s'arrêtent évoluent au maximum pendant 7 pas (resp. 25 et 145 pas) et elles ne produisent aucune suite plus longue que 3 bits (resp. 6 et 18 bits). Lorsqu'on passe à 5 états ces valeurs dépassent certainement 4000 et 47000000 respectivement mais elles ne sont pas connues avec exactitude.