Hao Wang, après avoir réinventé le modèle de calculateur universel de Post, a découvert avec ses étudiants que « paver, c’est calculer ».
par Alain Busser, Florian Tobé, Patrice Debrabant
On le sait peu, l’informatique théorique est née de questions que (se) posait David Hilbert sur les géométries non euclidiennes. En effet, troublé qu’il y ait des modèles cohérents de plusieurs géométries, euclidiennes ou non, il a transposé la question à la théorie des nombres, dans le second des problèmes de Hilbert [1]. Puis a étendu la question au problème de la décision. Et c’est pour s’attaquer à ce problème que les fondateurs de l’informatique théorique ont émis leurs théories en 1936 à Princeton : Gödel, Kleene, Post et même Turing, invité à Princeton en 1937. Mais le modèle de Post est un peu passé inaperçu jusqu’à 1954 où Hao Wang, logicien, l’a remise au goût du jour. D’autres travaux de Wang sur la logique, la calculabilité et les pavages seront évoqués dans cet article.
NB : Cet article, assez long, est organisé en blocs déroulants. Certaines illustrations essentielles sont cliquables, et mènent à des simulations de machines ou des jeux.
Machines à registres
Une image naturelle, d’ailleurs expérimentée en classe de collège [2], est inspirée des babyloniens qui mettaient des billes dans des sphères d’argile. On peut imaginer de placer des billes dans des boîtes en carton, ou des cases dessinées sur du papier. Les instructions élémentaires sont l’incrémentation (ajouter une bille), la décrémentation (enlever une bille si possible) et l’observation du caractère vide ou non, de la boîte. On peut donc assez facilement simuler ce genre de machine à registres illimités en langage de programmation Sophus [3].
Voici la version Sophus, avec l’interpréteur :
l’article | l’interpréteur sophus |
L’idée de Post (fin des années 1920) est de se limiter à des registres à 1 bit, c’est-à-dire que la boîte ne contient au maximum qu’une bille. Ou un coche (présent ou absent) comme ceci :
Antiposti au pays d’Alice
Des fouilles archéologiques ont mis à jour un lapin blanc, une Game Bille de Post/Wang et un test d’embauche pour cocheur chevronné.
Nous vous présentons ici les deux derniers.
La Game Bille de Post/Wang
En 1936, dans l’article intitulé « Finite combinatory processes - formulation 1 », Emil Post estime que le modèle qu’il vient de conjecturer, d’une simplicité extrême (d’après lui !), est « logiquement équivalent à la récursivité » ; l’histoire lui donnera raison...
En fait le modèle de Post utilise un procédé qui consiste en une séquence infinie de « boites » :
Une boite peut-être marquée ou non.
Initialement, un certain nombre (fini) de boites est marqué, les autres étant, de facto, non marquées.
Un « ouvrier » va alors se déplacer de boite en boite et manipuler une seule boite à la fois.
Ce faisant, il va marquer ou effacer une marque sur la boite en fonction des instructions qui lui ont été données.
Finalement les instructions feront effectuer les actions suivantes, très basiques, à cet ouvrier :
(a) Marquer la boîte devant laquelle il se trouve (à condition que celle-ci soit non-marquée),
(b) Effacer la marque de la boite devant laquelle il se trouve (à condition que celle-ci soit marquée),
(c) se déplacer vers la boite de droite,
(d) se déplacer vers la boite de gauche,
(e) Déterminer si la boite devant laquelle il se trouve est marquée ou non.
Ce set d’axiomes va permettre d’accomplir des tâches répétitives variées qui sont à la base de la programmation que nous connaissons aujourd’hui.
Nous vous proposons un « jeu » de conversion binaire dans lequel vous êtes cet ouvrier (Émilio Posti !) qui ne peut effectuer que les actions précédemment décrites. Saurez vous utiliser une démarche systématique pour progresser ? Vous seriez alors en mesure de décrire les instructions nécessaires à la conversion binaire !
(Remarques : avec le navigateur Safari 5 il n’y a pas de son...mais ça reste jouable ! Avec Internet Explorer c’est autre chose : Ce navigateur ne reconnaît pas le format audio vorbis, pourtant libre, ce qui empêche de mener les actions liées au son. Une solution serait de remplacer ce format par le MPEG-1/2 Audio Layer 3, mais celui-ci n’est pas libre, et moins bien géré par les mobiles...)
Si vous préférez télécharger ce jeu pour une utilisation en local, le voici :
Le test d’embauche pour cocheur chevronné
Ci-après, l’ouvrier qui est chargé de cocher des cases (selon le modèle binaire d’Emil Post, repris par Wang), s’appelle Emilio. Nous avons retrouvé les formulaires qui lui ont été soumis lors de son entretien d’embauche. Pour recruter un cocheur de cases, rien de mieux que lui demander de cocher des cases ! Voici donc les cases à cocher pour devenir cocheur de cases professionnel :
Le paradoxe d’Épiménide | Le paradoxe de Buridan | questions 3 | questions 4 | questions 5 | théorème de Gödel |
|
Les fichiers ci-dessus sont au format html, on est donc censé cliquer sur l’un d’entre eux pour le se tester. Mais leur légèreté fait qu’il est intéressant de les ouvrir avec un éditeur de texte pour voir comment est fait un fichier html.
de Post à Wang
En 1936, constatant que plusieurs définitions de la calculabilité émergeaient à Princeton, Emil Post a avoué avoir créé un modèle à registres binaires [4], qu’il a décrit comme un ensemble de chambres où un ouvrier (la machine de Turing) peut [5]
- accomplir un acte de vandalisme en plaçant une marque dans la chambre ;
- faire le ménage en enlevant la marque qu’il avait laissée auparavant ;
- voir si la chambre où il se trouve est propre (vide) ou non.
- Aller soit dans la chambre de gauche, soit dans celle de droite.
C’est le modèle que Wang Hao (logicien) a amélioré en 1954, en remplaçant l’ouvrier par une boîte à la Turing et les chambres par des cases sur une bande elle aussi similaire à celle de la machine de Turing. En fait il y a deux machines de Wang :
- La W-machine présentée ci-dessous et équivalente à la machine de Post.
- La B-machine, version simplifiée (mais équivalente tout de même) où l’encre de l’ouvrier est indélébile, ce qu’il fait que ledit ouvrier ne peut que cocher des cases, et pas les décocher après.
Voici donc Emilio Posti, célèbre ouvrier italien [6], qui, comme le montre le « W » sur sa casquette, travaille chez Wang incorporated, où il pose des carrelages (voir ci-dessous).
Chacun des exemples ci-dessous est un interpréteur en ligne. On peut modifier les instructions, cocher ou décocher des cases avant qu’Emilio les modifie, et tester en mode pas-à-pas.
- Tout d’abord, un algorithme sans grand intérêt juste pour voir comment ça fonctionne : Emilio est chargé de cocher toutes les cases vides vers la droite jusqu’à ce qu’il trouve une case déjà cochée, l’efface et s’arrête.
- Ensuite, un algorithme d’addition dans le système unaire. On représente les nombres par des « 1 » qui se suivent [7]. Avec la convention selon laquelle les deux nombres à additionner sont séparés par une seule case non cochée, il suffit pour effectuer l’addition, de décaler cette case vers la droite : La cocher et décocher une case à la place [8].
- Ensuite, la soustraction, toujours en base 1.
- Enfin la multiplication de 3 par 4 ; on code 3 par 111 et 4 par 1111, et à la fin Emilio laisse 12 cases consécutives cochées sur le plan de travail. La complexité de la tâche incite à la diviser en trois programmes qu’Emilio exécutera successivement, et à animer chacun d’entre eux automatiquement pour éviter d’avoir à cliquer trop souvent sur « un pas ».
mode d’emploi | premier algorithme | addition | soustraction | multiplication |
Post++
Ce qui va suivre semble inédit à ce jour, en tout cas ni Post ni Wang n’ont exploré cette voie [9] : Il s’agit de machines de Post bidimensionnelles [10]. Disons que le travail d’Emilio lui ayant valu d’être promu « cocheur de cases du mois », les établissements Wang Inc, qui l’emploient, lui offrent une promotion de préparateur de carrelages. Le langage de programmation de la machine de Post++ s’enrichit donc de deux nouvelles instructions :
- monter
- descendre
La frimousse d’Emilio a disparu, mais son ombre plane toujours sur la nouvelle grille de cases. En effet, le carrelage sur lequel travaille désormais Emilio étant vu de haut, on ne voit plus Emilio lui-même, mais seulement l’ombre rouge de sa casquette « W » sur le carrelage ;).
Quel est l’intérêt de cette nouvelle machine ?
Tout d’abord, de façon évidente, cette machine, qui se présente comme un automate cellulaire à tête de lecture, permet d’implémenter l’évolution de certains automates cellulaires particuliers, dont le programme en Post Wang++ peut être considéré comme une signature « naturelle » (le Post Wang++ étant lui-même un langage de programmation simple et naturel).
On peut par exemple programmer une fourmi de Langton (on notera que contrairement à la fourmi traditionnelle, Emilio ne tourne pas sur lui-même) et la voir s’acharner à creuser un tunnel jusqu’à plus soif (= jusqu’à plus de cases). (Si on a pitié de la fourmi, on peut lui simplifier un peu l’existence en cochant une case à droite d’Emilio avant de lancer le programme.)
Les exemples ci-dessous montrent
- La-dite simulation de la fourmi de Langton ;
- un automate cellulaire monodimensionnel (« règle 90 ») dessinant un triangle de Sierpiński...
fourmi de Langton | triangle de Sierpiński |
En ce qui concerne la calculabilité, on pourrait penser que ce passage en 2D ne va pas apporter pas grand-chose de plus. En effet, la machine de Post Wang unidimensionnelle étant équivalente à une machine de Turing, elle est déjà potentiellement capable de calculer tout ce qui est calculable.
Tout est dans le « potentiellement ». En pratique, on l’a vu dans les exemples précédents, programmer des fonctions simples avec la machine de Post Wang unidimensionnelle s’avère assez vite compliqué. Une soustraction, une multiplication... On ne va pas très loin.
On peut faire un parallèle avec les machine de Turing à symboles multiples : ces machines potentiellement équivalentes permettent d’implémenter en pratique des fonctions qu’il serait très difficile de réaliser avec une machine de Turing à deux symboles. Et cette implémentation se fait dans un modèle qui reste simple.
La machine de Post Wang bidimensionnelle peut être considérée comme un concurrent des machines de Turing à symboles multiples. Car comme on va le voir, avec cette nouvelle machine on est capable d’écrire des programmes de fonctions qui semblaient inaccessibles.
Dans cette nouvelle perspective, on envisage des données et des résultats en ligne.
Alors, qu’est-ce que l’on va pouvoir calculer ? Et comment faire ?
1) Tout d’abord, on peut utiliser l’espace vertical pour se déplacer plus librement et éviter les obstacles.
Cela permet de programmer sans grande difficulté une addition ou une soustraction en binaire.
Pour ces deux exemples, les deux premières lignes représentent les opérandes (non modifiés durant l’opération) et la troisième ligne, le résultat.
addition binaire++ | soustraction binaire++ |
La multiplication binaire est cependant beaucoup plus difficile à programmer ainsi, parce que le plateau de jeu est potentiellement infini et qu’il est difficile pour Emilio de savoir quand passer à l’étape suivante du calcul (aller à la ligne, commencer à effectuer les additions, etc).
Mais on va y revenir. Après un petit détour...
2) Ensuite, et surtout, on peut exploiter une « géométrisation » du calcul (en base 1), qui permet de programmer plus aisément.
Qu’entend-on par une « géométrisation » du calcul ?
C’est l’association d’un type de calcul avec une configuration géométrique.
L’exemple le plus simple est celui de la multiplication. Sa « géométrisation » est une position des deux facteurs qui permet aisément de « dessiner » l’aire, ce qui permettra ensuite de la calculer sur une ligne en « l’aplatissant ».
géométrisation-produit |
* Multiplication :
En résumé, Emilio utilise le programme 1 pour « géométriser » le calcul et le programme 3 pour « l’aplatir » ; l’algorithme de multiplication proprement dit est le programme 2 qui n’occupe plus que 17 lignes… Ces trois programmes pourraient bien-sûr être fondus en un seul.
multiplication unaire++ |
Mais on dira que l’on disposait déjà d’un programme de multiplication pour la machine mono-dimensionnelle.
Soit. Essayons d’aller plus loin.
* Soustraction :
La géométrisation est la même que pour le produit.
Il suffit de « rabattre » la colonne sur la ligne pour effacer les cases voulues.
soustraction unaire++ |
* Reste entier :
La géométrisation est la même que pour le produit.
Ensuite on dessine l’aire, on efface les carrés pleins, et et on garde la ligne supérieure de l’aire résiduelle.
reste-entier unaire++ |
* Quotient entier :
La géométrisation est la même que pour le produit.
Mais on a besoin d’une ligne en haut pour stocker le quotient. Donc on décale l’ensemble d’une ligne vers le bas (prog 1).
Puis on géométrise (programme 2)
Enfin on dessine l’aire et on marque une case bouée au niveau du quotient (ligne 2). On efface tous les carrés pleins (boucle) et à chaque fois qu’on a effacé un carré on ajoute 1 au quotient (ligne 2). Quand on n’arrive plus à trouver un carré plein, on efface ce qui reste et on retourne à la ligne 2 pour effacer une case (ce qui revient à enlever la bouée). (programme 3)
quotient-entier unaire++ |
Sur cet exemple, on notera qu’il peut être utile en Post de poser des cases bouées pour fixer certains éléments sur la grille.
* Puissance :
Cet exemple illustre bien une nouvelle difficulté de la programmation en Post++ quand on veut enchaîner plusieurs fois le même programme (la puissance est un cas typique).
Imaginons que l’on veuille calculer 3^5.
Une idée naturelle serait de géométriser ainsi :
Ensuite, on ferait le produit. Puis on aplatirait et on obtiendrait ceci :
On pourrait alors recommencer en 1) (boucle).
Pour multiplier, le programme produit vu plus haut utilise la colonne juste à gauche de l’aire qui va être dessinée. Cette colonne doit être vierge.
On opte donc pour une géométrisation un peu différente que voici :
géométrisation-puissance |
Une transition à chaque itération (on itère 5 fois le produit) raménera à une configuration produit.
D’autre part, on commence par inverser les deux opérandes pour arriver plus facilement à la configuration-puissance.
En résumé :
On inverse les opérandes.
On fait une géométrisation-produit.
On dessine l’aire.
On ajuste pour obtenir la géométrisation- puissance. (programme 1)
Puis (en boucle) :
- On calcule un produit (= dessin de l’aire + aplatissement)
- On ajuste pour retrouver une géométrisation puissance.
Enfin, on gère les phases terminales. (programme 2)
puissance unaire++ |
* PGCD :
L’idée de base est la suivante :
Imaginons que l’on soit dans une géométrisation-produit.
Si on applique un programme Reste, on obtient en haut (ligne 2) à droite le reste.
Si on écrit à droite de cette géométrisation-produit le plus petit nombre, ça ne perturbe pas le programme et on obtient un truc sur lequel on peut boucler : plus petit, espace, plus grand.
Voici la géométrisation-PGCD (pour 8 et 3) :
géométrisation-PGCD |
|
Le reste s’appliquant à plus grand, plus petit, on commence par inverser les opérandes.
En résumé :
- prog 1 : inversion des opérandes.
- prog 2 : géométrisation-PGCD.
- prog 3 : programme Reste appliqué à la géométrisation-PGCD. On obtient plus petit espace plus grand.
Et on peut alors réitérer prog 1, prog 2 et prog 3 jusqu’à obtenir le PGCD.
Remarque : dans cette version, la phase terminale n’est pas parfaitement gérée.
Le problème est réglé dans la version in-One qui regroupe les trois programmes, calcule le PGCD, et gère la phase terminale en un seul programme.
PGCD1++ | PGCD-in-One++ |
Revenons maintenant aux opérations en binaire.
On a dit plus haut que la multiplication en binaire était compliquée à programmer en Post++.
Mais comme on vient de le voir, on peut réaliser un certain nombre d’opérations en unaire…
La tentation est donc grande de programmer des convertisseurs binaire ↔ unaire.
Et c’est ce que l’on va faire maintenant.
Commençons par la conversion unaire → binaire.
C’est la plus simple des deux car on n’est pas confronté à l’épineux problème suivant : quand on écrit un nombre en base 2 avec deux symboles on ne peut pas distinguer à gauche s’il s’agit d’un zéro ou de la fin du nombre (=la plus grande puissance de 2 +1). On verra plus loin comment cette difficulté sera contournée.
Conversion unaire → binaire :
* Version 1 :
Le nombre en unaire est initialement sur la ligne 5.
On commence par placer une bouée en (2 ,2) pour fixer les positions binaires. A droite de cette position, on aura la position des unités, puis celles des deuzaines, etc.
Le résultat en binaire sera écrit en dessous.
Par conséquent l’écriture du résultat en binaire sera inversée. Cela sera rectifié plus tard. Comme on a pris l’habitude de progresser de gauche à droite, il est plus commode de commencer par procéder ainsi.
On décale ensuite le nombre d’une case vers la droite et vers le bas.
Sur la ligne 5 ainsi libérée, on placera le quotient en unaire. On place une bouée en (5,5).
La ligne 4 sera utilisée pour placer une bouée mobile qui indique où en est dans le traitement du nombre.
On remplit donc la ligne 5 jusqu’à arriver au reste modulo 2.
On place une bouée 2 cases plus à droite (au cas où le reste serait nul).
Puis on vient ajouter une nouvelle position au résultat en binaire.
On retourne alors à la bouée que l’on vient de poser et si le reste (deux cases à gauche) n’est pas nul, on va ajouter un 1 au résultat binaire.
Enfin, on retourne supprimer la bouée et le reste et on revient ligne 5 pour effacer la bouée du quotient unaire.
_Et on peut alors recommencer le traitement.
La phase terminale n’est pas parfaitement réglée. Elle le sera dans la version suivante.
lecture du résultat dans la première version de travail |
|
* Version 2 :
Dans cette version, le programme itére les étapes et gère la phase terminale. On obtient en une fois le résultat en binaire (en écriture inversée).
* Version finale :
Pour régler le problème de l’inversion de l’écriture, il suffit d’opérer une symétrie axiale, ce qui se fait facilement en remplaçant gauche par droite dans toutes les lignes du programme.
On obtient un alignement à droite et le résultat attendu.
ConversionUnaireVersBinaire-1++ | ConversionUnaireVersBinaire-2++ | ConversionUnaireVersBinaire-final++ |
Conversion binaire → unaire :
Le problème déjà évoqué plus haut de représentation d’un nombre binaire avec deux symboles incide à concevoir un algorithme qui va calculer les puissances de 2 plutôt que de multiplier par 2 à chaque itération (car il faudrait savoir où on commence).
On va donc utiliser le programme de calcul d’une puissance.
* Version 1 :
Dans le programme 1, on part d’un nombre en binaire écrit à l’envers en (3,2) sur la ligne 2 . Mario est devant. (3,2) correspond au chiffre des unités.
On commence par placer une bouée en (2,4). Le résultat en unaire sera écrit sur la ligne 4 (avec une bouée en plus).
_On place une autre bouée-puissance en (3,6) pour fixer les calculs de puissances.
_Puis, en boucle :
- On circule sur la ligne 2 en marquant par une bouée mobile au dessus (en L1) à quel rang on est ;
- Si on rencontre une case cochée, on calcule la puissance (la bouée-puissance permet de savoir quelle puissance) et on ajoute le résultat en L4.
Le programme 2 permet de faire le ménage et d’enlever la bouée dans le résultat. Mais il faut le lancer au moment opportun...
La phase terminale dans le programme 1 n’est pas gérée, et c’est inévitable compte tenu du problème de représentation des nombres binaires avec deux symboles : Emilio ne cesse d’aller à droite pour trouver une case cochée et finit par s’écraser sur la colonne de droite.
Ce problème sera traité dans la version finale.
* Version finale :
Pour éviter le problème de l’inversion, on reprend tout le code des programmes et on remplace gauche par droite. Cette fois, Emilio vient s’écraser à gauche.
L’astuce (qui est un peu un truandage...) consiste alors à gérer la sortie par la gauche (colonne de gauche) sur la ligne 1.
Quand ça se produit, on bascule sur le programme 2, qui fait le ménage et devrait normalement venir se replacer à droite du résultat.
Mais l’astuce est reproduite par commodité (cette fois ce n’était pas indispensable) :
quand on sort par la gauche sur la ligne 3, on bascule sur le programme 3, qui vient replacer Emilio devant le résultat de sa conversion.
Contrairement aux apparences, on ne doit pas lancer les programmes 2 et 3, tout est automatique : on lance le programme 1 (qui lui-même lancera le 2,...) et on obtient la conversion.
On peut considérer que l’astuce revient à travailler sur un demi-plan de cases, la colonne de gauche servant de barrière et permettant de basculer d’un programme au suivant.
ConversionBinaireVersUnaire-1++ | ConversionBinaireVersUnaire-final++ |
Et la boucle est bouclée : pour faire une opération en binaire, on peut utiliser le convertisseur et faire l’opération en unaire.
Remarque : les deux programmes suffixés final sont considérablement ralentis par le fait que l’on affiche à chaque étape le nombre de départ et le résultat. Voici une version plus rapide sans cet affichage dynamique :
ConversionRapideUnaireVersBinaire-1++ | ConversionRapideBinaireVersUnaire-final++ |
Pour terminer, signalons que la technique utilisée ici permettrait même à Emilio de résoudre des problèmes sur les graphes, mais ce serait très long à programmer.
Calcul par pavages de Wang
Wang a inventé ses machines, équivalentes à une machine de Turing, en 1955-1956.
Dans la partie précédente, on a construit ces mêmes machines et quelques variantes. Toutes ces machines sont capables de calculer n’importe qu’elle fonction calculable.
On va maintenant s’intéresser à un autre sujet introduit (puis exploré) par Wang en 1961 : les tuiles de Wang.
Les tuiles de Wang sont des carrés à bords distincts (traditionnellement colorés ou découpés) qui s’assemblent comme des pièces de puzzle dans le plan à deux dimensions.
Mais (contrairement à un puzzle) les pièces peuvent seulement être glissées (les rotations et les symétries ne sont pas permises). Voici par exemple un jeu de tuiles :
Avec ces tuiles, on cherche à paver une zone rectangulaire du plan, voire le plan tout entier.
Avec le jeu de tuiles précédent, on peut réaliser le pavage suivant (qui est périodique [11]) :
Remarque : les mêmes tuiles peuvent être vu comme des pièce de puzzle avec des bords découpés, ou coloriés différemment.
Voici par exemple un jeu de tuiles à bords découpés (et un équivalent coloré) :
Avec ces tuiles, on peut réaliser ce pavage :
De prime abord, le sujet peut sembler tout simple et on se dit que les logiciens vont le manger tout cru.
Mais il n’en est rien : le sujet recèle des pépites de complexité qui le rendent difficile à digérer.
Wang avait inventé ces tuiles pour incarner des notions abstraites de calculabilité et il pressentait certainement leur potentiel. Mais il restait à mesurer précisément ce potentiel.
Dès leur introduction, Wang s’était intéressé au pavage du plan par ces tuiles. Et il s’était aventuré à conjecturer que le problème du pavage du plan par un jeu fini de dominos était décidable (autrement dit qu’il existait un algorithme capable de décider en temps fini si un jeu de tuiles peut paver ou non le plan).
Cette conjecture était la conséquence logique d’une autre conjecture : « tout pavage du plan avec un nombre fini de tuiles, est périodique [10] ».
Tout cela semblait naturel et rassurant jusqu’à ce que cette conjecture soit réfutée en 1966 par Berger, un élève de Wang. La tuile…
Le sujet s’avérait ainsi plus complexe que prévu, et plus intéressant aussi. On pouvait alors reprendre les choses à l’envers et réfuter la conjecture initiale : il devait nécessairement exister des pavages apériodiques (ceux-ci feront l’objet de la dernière partie de cet article).
On pourrait dès maintenant préciser le potentiel des tuiles de Wang mais on va différer cet exposé et commencer par l’illustrer par des exemples concrets. Comme on va le voir, en inventant ses tuiles, Wang n’était pas si loin de ses machines...
Qu’est-ce qu’on peut faire avec des tuiles de Wang ? Eh bien, pourquoi pas du calcul ?...
Revenons donc à Emilio. Toujours selon le principe de Peter, celui-ci a obtenu sa promotion comme carreleur : Il va enfin travailler à l’extérieur des établissements Wang, en posant des carreaux sur les vérandas de personnalités de la jet-set. Pour chacune des missions d’Emilio en extérieur, les établissements Wang lui confient un jeu de carreaux qu’il doit poser en respectant l’ajustement des couleurs et des formes entre carreaux. On peut l’aider en déplaçant des pièces à l’écran, ce qui revient à résoudre un puzzle. Mais Wang a en réalité caché des calculs dans le jeu de pièces de puzzle...
- Les fichiers suivants sont des pavages additionneurs. Le premier réalise une addition par translation [12]. Il est dû à Branko Grünbaum et Geoffrey Collin Shephard [13]. Une variante est fournie dans laquelle les carreaux ont une forme de croix (signe « + ») et sont disponibles en grande quantité, parce que c’est cette forme de croix que prend spontanément l’ADN [14]. et le dernier pavage est une adaptation en base 10 de l’additionneur de Yuriy Brun ci-dessous (voir l’additionneur binaire).
le pavage additionneur | la version ADN | L’additionneur décimal |
- Comme l’indique le titre de cet article, « paver c’est calculer ». Lorsqu’on fait un pavage de Wang, on a parfois du mal à savoir ce qu’on est en train de calculer exactement. Le premier fichier ci-dessous calcule la suite des coefficients binomiaux modulo 2 : Encore le triangle de Sierpinski ! En pavant la salle, Emilio représente par des carreaux rouges les nombres impairs du triangle de Pascal, et en bleu les nombres pairs (0 étant pair, les nombres qui ne sont pas dans le triangle de Pascal sont aussi représentés en bleu). Le second fichier calcule tout simplement la suite arithmétique de raison 1 (la suite des entiers) en binaire. C’est donc un compteur binaire :
le jeu de puzzle de Sierpinski | Le compteur binaire |
- On peut d’ailleurs effectuer des opérations en binaire, avec des algorithmes de Yuriy Brun [15].
addition binaire de deux octets par pavage de Wang | soustraction binaire | multiplication binaire par pavage |
Conclusion :
Dans les annèes 1950, on connaissait plusieurs définitions équivalentes de la calculabilité : Machines de Turing, Lambda-calcul, fonctions récursives, machines de Post et Wang, « tag-systèmes » de Post, systèmes de réécriture de Markov. Mais à la fin des années 1950, Hao Wang a trouvé un autre modèle de calculabilité dont il a montré l’équivalence avec la machine de Post-Wang, donc avec toutes les autres aussi : Des puzzles [16], comme on vient de l’illustrer.
Wang était logicien, donc les fonctions calculables auxquelles il s’intéressait le plus étaient les propositions : Wang appelait décidable une proposition telle qu’il existe une machine de Turing permettant de dire si elle est vraie ou fausse. On peut étendre cette définition à une théorie. Wang croyait que les pavages de Wang sont décidables, autrement dit, qu’il existe un algorithme (qu’il s’évertuait à trouver...) qui, en entrée, reçoit un jeu de pièces de puzzle, et qui répond si il est possible de paver tout le plan avec ce genre de pièces. En fait, Wang a montré que cette conjecture se déduisait de celle selon laquelle, à chaque jeu de puzzle solvable (pavage du plan) pouvait correspondre une solution périodique. Mais en 1966, Robert Berger, un étudiant de Wang, a prouvé qu’un algorithme général qui permettrait, rien qu’en voyant un jeu de pièces de puzzle, de dire s’il est solvable, n’existe pas [17] [18]. Par contraposition, il en a donc déduit l’existence d’un pavage apériodique du plan. Le premier du genre. D’autres ont suivi, comme celui de Raphael Robinson, ceux d’Amman, de Penrose, et pus récemment ceux de Kari et Culik.
C’est à ces pavages apériodiques que l’on va maintenant s’intéresser.
Les pavages apériodiques
Remarque : pour éviter une confusion, on parlera plus volontiers de jeux apériodiques de tuiles que de pavages apériodiques.
L’existence de jeux apériodiques de tuiles étant aquise, on a naturellement cherché à en exhiber.
Berger avait initialement trouvé un jeu apériodique de 20 426 (!) tuiles. Il a réussi à réduire ce nombre à 104 tuiles. Puis Knuth a encore réduit ce nombre à 96.
Pour réduire encore le nombre de tuiles, différents chercheurs ont adapté des pavages apériodiques existants pour en faire des jeux apériodiques de tuiles de Wang.
http://grahamshawcross.com/2012/10/12/wang-tiles-and-aperiodic-tiling/
Parmi les pavages obtenus de cete manière, on peut relever les pavages de :
– Robinson, 1971 (4x6 = 24 tuiles)
Il suffit ici pour obtenir des dominos de Wang de dupliquer 4 fois chaque pièce (avec rotations d’un quart de tour) pour obtenir des dominos à glisser.
– Roger Penrose, 1986 (32 tuiles)
On part d’un pavage par flèche et chevron :
Et on obtient ce jeu de tuiles :
– Amman, 1986 (16 tuiles)
On utilise ces motifs :
Et on obtient ce jeu de tuiles :
Tous ces pavages sont obtenus et démontrés apériodiques par des considérations géométriques.
En 1995, Kari propose une méthode révolutionnaire pour obtenir un pavage apériodique. Celui-ci est de nature algébrique, et s’appuie sur un type de machine sans ruban, la Mealy-machine.
Par cette méthode, il obtient un pavage apériodique à 14 tuiles (en fait 13, une des tuiles n’étant pas utilisée au final, comme il le démontrera plus tard).
Kulik adapte légèrement la méthode pour obtenir un autre pavage apériodique à 13 tuiles.
A chaque fois, le jeu de tuiles donne une infinité de pavages sans période.
Par ailleurs le jeu de tuiles peut être coloré de différentes façons car les couleurs horizontales et verticales sont indépendantes (pour limiter le nombre de couleurs, on prend souvent les mêmes horizontalement et verticalement).
Voici par exemple deux colorisations du jeu de tuiles de Culik (ces tuiles sont données ici sans égard à la façon dont elles ont été générées) :
On peut alors envisager de jouer à reconstituer un pavage apériodique en masquant son origine, ce qui peut s’avérer assez difficile :
le puzzle d’Ammann | le puzzle de Culik | le puzzle de Kari |
Démontrer que le pavage de Robinson ou celui d’Amman sont périodiques est un exercice intéressant mais disons-le assez assommant : il faut étudier finement les motifs qui apparaissent nécessairement dans un pavage, les classer..., pour finalement exclure toute possibilité de périodicité.
On va ici se concentrer sur le pavage de Culik (il est plus juste de le qualifier de pavage de Kari et Culik car il doit beaucoup à Kari). Commençons par le présenter, implémenté en HTML/Javascript, puis avec DGPad.
Dans le premier fichier DGPad, le script est « prédigéré », ce qui permet un chargement rapide. Dans le second, on a le vrai script du pavage et le chargement est nettement plus long.
Pavage de Culik (HTML) | Pavage de Culik (DGPad) | Pavage de Culik 2 (DGPad) |
Remarque : les figures DGPad ont été exportées avec tableau de bord, ce qui permet d’accéder à leur code source.
Comment est construit ce pavage ?
La première idée, somme toute assez naturelle, consiste à interpréter un jeu de tuiles comme une machine de Mealy.
Qu’est-ce qu’une machine de Mealy ?
Il s’agit en quelque sorte d’une machine de Turing sans ruban : la machine possède différents états. Dans un état donné, la machine peut lire un symbole en entrée ; elle donne alors en sortie un symbole, et change d’état.
Les états seront les côtés verticaux (gauche -> droite) des tuiles et les symboles lus et produits seront les côtés horizontaux (haut -> bas).
Dans le cas du pavage de Kari, la machine sera déterministe. Dans le cas du pavage de Culik, la machine sera non déterministe (mais appliquée de façon déterministe pour éviter les culs de sac).
Les symboles lus et produits seront des nombres. Pour garantir l’apériodicité de tout pavage, on va en quelque sorte créer une machine de Mealy qui peut soit multiplier par 3, soit multiplier par 1/2. Un produit de facteurs 3 et 1/2 ne donnant jamais 1, on ne pourra pas retrouver le nombre de départ, ce qui interdira toute périodicité.
Sur chaque ligne, on « codera » un nombre et sur la ligne du dessous on codera son produit par q (3 ou 1/2).
C’est ici que ça se complique. L’objectif est d’obtenir une version faible (mais suffisamment forte pour conclure à l’apériodicité) de la vue de l’esprit suivante : « la ligne du dessous est obtenue en multipliant la ligne du dessus par 3 (respectivement par 1/2). Chaque tuile de la ligne va donc multiplier par 3 (respectivement par 1/2). »
Seulement, il ne faut pas rêver : si une tuile multipliait effectivement par 3 ou 1/2, il y aurait clairement une infinité de côtés horizontaux et donc de tuiles…
On va donc amortir par les états.
Considérons une tuile :
On va imposer non pas c=qa (avec q=3 ou 1/2) mais qa+b = c+d (amortissement par les états).
Autrement dit : c = qa - (d-b)
d-b est le changement d’état.
Vérifions que ce dispositif s’intègre dans la vue de l’esprit :
Imaginons alors un pavage qui serait périodique avec un motif rectangulaire qui se répète.
Intéressons-nous à la somme $S_1$ des côtés supérieurs de la ligne du haut. Soit $S_2$ une ligne en dessous.
c = qa - (d-b) donc en sommant sur le motif on obtient $\Sigma (d-b)=0$ par périodicité, donc $S_2=q.S_1$.
Autrement dit, quand on parlait de ligne dans la vue de l’esprit, il s’agit en fait de la somme (hypothétique) des côtés supérieurs sur un motif rectangulaire périodique.
On obtiendra de même $S_3=q.S_2$, etc…
Et arrivé à la dernière ligne du motif on doit retrouver $S_1$ par périodicité.
Si $S_1 \neq 1$, on aboutira alors à une contradiction (car un produit de 3 et de 1/2 ne donne jamais 1).
Reste à construire les tuiles.
Il y a deux contraintes :
- on veut qu’il n’y ait pas trop de tuiles ;
- on veut pouvoir appliquer la machine de Mealy dans les quatre directions.
L’dée géniale de Kari consiste à convoquer les suites de Beatty, et même leur première différence (oui, il fallait y penser !…).
Pour un réel $r$, on note $\lfloor r \rfloor$ la partie entière de r.
Etant donné un nombre $\alpha$, sa suite bi-infinie de Beatty $B(\alpha)$ est la suite $B(\alpha)_i = \lfloor i \alpha \rfloor$.
Les suites de Beatty ont été introduites par Beatty en 1926.
Kari a utilisé les suites obtenues en calculant les premières différences des suites de Beatty.
Pour $i \in \mathbb{Z}$, on définit $E(\alpha)_i = B(\alpha)_i – B(\alpha)_{i-1}$
Cette suite bi-infinie sera appelée la representation équilibrée de $\alpha$. Cette représentation équilibrée est en fait une suite de deux entiers. En effet, si $k\leqslant \alpha \leqslant k+1$, alors $E(\alpha)$ est une suite de k et de k+1.
Par exemple :
$E(1,5)= ….121212 …$, $E(\frac{1}{3})= ... 001001 ….$, $E(\frac{8}{3})= … 233233 ….$.
Le nombre lu sera de la forme $E(\alpha)_i$
Le résultat sera $E(q.\alpha)_i$
Pour rétablir l’amortissement par les états (qa+b = c+d) la différence des états doit être égale à $qE(\alpha)_i-E(q.\alpha)_i$
Pour obtenir cette différence, on prend naturelllement comme état $qB(\alpha)_i – B(q.\alpha)_i$. Cet état fait l’amortissement voulu.
Pour q=3, $q\lfloor r \rfloor - \lfloor qr \rfloor $ est égal à -2, -1 ou 0 (3 états).
Pour q=$\frac{1}{2}$, $q\lfloor r \rfloor - \lfloor qr \rfloor $ est égal à 0 ou à $\frac{1}{2}$ (2 états).
On va faire en sorte que $\alpha$ (qui sera multiplié par 3 ou $\frac{1}{2}$) reste toujours compris entre 0 et 2. Ainsi le nombre lu sera forcément 0,1 ou 2.
Plus précisément, si $\alpha \in [\frac{1}{3},\frac{2}{3}]$, on lira un 0 ou un 1 et on multipliera $\alpha$ par 3.
Ce qui correspond à la machine de Mealy $M_3$ suivante :
Et de la même façon, si $\alpha \in [0,2]$, on lira un 0, un 1 ou un 2 et on pourra multiplier $\alpha$ par $\frac{1}{2}$.
Ce qui correspondrait à la machine de Mealy $M_{\frac{1}{2}}$ suivante :
Mais il y a clairement un problème : la tuile (0,0,0,0) (et son équivalent pour l’état 1/2), qui n’a rien d’apériodique...
Dans l’esprit, il faut continuer à multiplier par 3 et $\frac{1}{2}$ à l’infini. Et $\alpha$ ne doit jamais descendre en dessous de $\frac{1}{3}$.
Pour arriver à ce résultat, on va modifier la machine $M_{\frac{1}{2}}$ en $M’_{\frac{1}{2}}$ pour faire en sorte qu’elle ne puisse pas s’appliquer plus de deux fois de suite sur une ligne. On introduit donc un nouveau symbole d’entrée/sortie 0’. Et on introduit aussi un nouvel état 0’ pour faire en sorte que les états de $M_3$ et $M’_{\frac{1}{2}}$ soient disjoints. Ainsi, on peut considérer que la réunion de $M_3$ et $M’_{\frac{1}{2}}$ constitue une seule machine de Mealy.
Cette machine de Mealy permet de construire une infinité de pavages valides du plan.
Il suffit de partir d’une suite $E(\alpha)$ avec $\alpha \in [\frac{1}{3},2]$.
Si $\alpha \in [\frac{1}{3},\frac{2}{3}]$, on multiplie $\alpha$ par 3.
Sinon on multiplie $\alpha$ par $\frac{1}{2}$. Et dans ce dernier cas, si on est encore supérieur à $\frac{2}{3}$, alors on multiplie encore $\alpha$ par $\frac{1}{2}$. Et cette fois, on est dans $[\frac{1}{3},\frac{2}{3}]$.
Le jeu de tuiles est le suivant :
Ce jeu de tuiles est apériodique car on peut considérer que $S_1$ correspond à une ligne où l’on multiplie par 3, et on voit bien que dans ce cas (sauf cas trivial à écarter) $S_1>0$ .
Pour aller plus loin :
Une suite de Beatty est associée à un nombre irrationnel x [19] ; il y a donc autant de suites de Beatty que de nombres irrationnels, c’est-à-dire ... beaucoup ! La suite de Beatty associée à x a pour terme général la partie entière de nx. Le théorème de Beatty (en réalité, de Rayleigh) dit que le complémentaire de la suite de Beatty de x (c’est-à-dire les entiers qui ne sont pas dans la suite de Beatty de x) est la suite de Beatty de 1-1/x.
Kari et Culik utilisent non pas la suite de Beatty B(n), mais sa première différence B(n+1)-B(n). Celle-ci est bornée, et même, ne prend que deux valeurs. Pour une fraction, la suite de Beatty différenciée est périodique. Ensuite, Kari regarde l’effet sur sa suite de Beatty différenciée, d’une multiplication d’un nombre par une fraction. Et s’en sert pour encoder sous forme de transformations de suites de Beatty, un système dynamique n’ayant pas d’orbites finies. Ensuite il ne lui reste plus qu’à traduire l’algorithme en un pavage de Wang, et celui-ci est apériodique parce que le système dynamique l’est. Le nombre de pavés obtenu par ce genre de construction est un record à l’heure actuelle (14 puis 13 chez Kari, 13 chez Culik).
Voici des fichiers interactifs illustrant tout ça :
suites de Beatty | systèmes dynamiques |
Biographie d’Hao Wang
Hao Wang est né le 20 mai 1921 à Jinan en Chine. Il avait donc 15 ans lorsque Church et Turing se disputaient la paternité de la notion de calculabilité. Diplômé en philosophie à l’université de Pekin, il a quitté sa Chine natale pour prolonger ses études dès la fin de la seconde guerre mondiale. En l’occurence, il a soutenu sa thèse de doctorat en 1948 à Harvard [20]. C’est donc l’un des rares personnages de cette histoire qui n’ait pas travaillé à Princeton. Néanmoins, il est parti en 1950 à l’école polytechnique fédérale de Zurich étudier la logique avec Paul Bernays, un ancien collaborateur de Hilbert. C’est donc en 1954 qu’il a affiné le modèle de Post avec la W-machine vue ci-dessus, puis sa simplification la B-machine. La présentation de 1954 a abouti à une publication en 1957 [21].
Voici comment Wang imaginait la machine de Wang (qu’il appelait « de Turing ») :
La molette « memory dial » est le compteur programme qui indique 1 au départ, puisque la machine s’apprête à lire la ligne 1 du programme.
En 1959, Hao Wang a créé l’un des premiers logiciels de démonstration automatique de théorèmes. Il a enseigné la logique à l’université Rockefeller à New-York.
En 1961, Hao Wang a continué ses recherches sur la décidabilité dans la logique du premier ordre. Pour expliquer une notion quelque peu abstraite liée à ces questions, il a inventé un problème dit « des dominos » puis rebaptisé « des pavages de Wang », dont son étudiant Robert Berger a montré l’indécidabilité en 1966.
Dans les années 1970, Wang a interviewé Gödel à propos des implications philosophiques de sa vision de la logique [22], et, après le décès de celui-ci, a collecté des notes prises lors de ces interviews dans des publications comme celle-ci.
Hao Wang est décédé le 13 mai 1995. Apparemment il était gaucher :
- portrait de Wang (couverture d’un de ses livres)
- Le demi-visage en fond est celui de Kurt Gödel, dont Wang a été le confident à la fin de sa vie, et qui a connu Post et Turing dans leurs travaux à Princeton