Est-ce que ça s’arrête ?
Piste rouge Le 10 juillet 2009 Voir les commentaires (1)
Nous présentons divers problèmes de terminaison, dont la solution est plus ou moins facile et nous évoquons les applications de la terminaison en logique mathématique et en informatique.
Des petits cailloux
Des rouges, des bleus
Imaginez un alignement de petits cailloux colorés rouges et bleus qu’une petite main s’amuse à modifier. Elle le fait suivant certaines règles précises ; elle considère une petite zone et y déplace des cailloux mais elle peut aussi en ajouter. Elle peut, par exemple, le faire en appliquant la règle suivante :
- règle 22 donne 22
Ça veut dire que quand il y a deux cailloux rouges suivis de deux bleus, la petite main échange les rouges et les bleus. Avec cette règle, la petite main peut faire les transformations suivantes :
- Exemple pour 22 donne 22
On voit que, quoi qu’elle fasse, elle ne peut pas déplacer les cailloux indéfiniment ; en effet, le nombre de cailloux ne change pas, et même plus précisément le nombre de cailloux bleus et le nombre de cailloux rouges ne changent pas. Mais ce qui change, c’est le fait que les cailloux bleus soient déplacés vers la gauche et il y aura un moment où la petite main ne pourra plus déplacer les cailloux bleus vers la gauche !
En revanche, si la petite main s’autorise à ajouter aussi des cailloux suivant la règle
alors elle ne s’arrêtera pas, car le motif constitué de deux boules rouges suivies de quatre boules bleues se reproduit en lui-même indéfiniment.
Plus précisément, cela donne
- example 22 donne 44
Si la petite main s’autorise à déplacer et à ajouter des cailloux, un bleu et un rouge, suivant la règle
cela donne par exemple :
Va-t-elle s’arrêter de partant de la configuration ci-dessus ? Va-t-elle s’arrêter quelle que soit la configuration de départ ? [1]
La terminaison uniforme
Dans cet article, nous nous intéressons à la terminaison uniforme, on dit aussi l’arrêt, c’est-à-dire que nous tentons de répondre à la question « Le procédé de transformation s’arrête-t-il dans tous les cas ? » Un procédé s’arrête quand il n’y a plus rien à faire. Dans notre cas des alignements de cailloux, on s’arrête quand en cherchant partout dans l’alignement on ne trouve pas de configuration de cailloux qui puisse être transformée par la petite main en utilisant l’une des règles. La terminaison [2] est dite « uniforme » parce dans le cas où il y a plusieurs transformations possibles, on n’en privilégie aucune.
Des rouges, des bleus, des verts
Maintenant supposons qu’il y ait aussi des cailloux verts et les règles :
Autrement dit, deux rouges donnent un bleu suivi d’un vert, deux bleus donnent un rouge suivi d’un vert, deux verts donnent un rouge suivi d’un bleu.
Est-ce que ça va s’arrêter [3]. Ou non ?
Des noirs
Maintenant les cailloux sont tous de la même couleur, mais on regarde les alignements plus globalement, [4].
Quand on avait des couleurs, on pouvait regarder des configurations comme trois rouges — trois bleus, maintenant on examine tout l’alignement et on regarde si on peut faire des regroupements, par exemple, deux paquets de même taille (premier cas) ou deux paquets presque de même taille (deuxième cas). Dans le deuxième cas, je veux dire par « presque » qu’on a deux paquets de même taille plus un caillou restant [5].
Supposons qu’il y ait deux règles :
La terminaison est facile et je suppose que vous voyez pourquoi le processus ne peut pas « diverger ».
Considérons maintenant deux règles plus difficiles :
qui veulent dire que si on peut rassembler les cailloux en deux groupes [6] de même taille, la transformation enlève un de ces groupes, et si au contraire on ne peut pas assembler les cailloux en deux groupes de même taille, alors on peut les assembler
en deux groupes de même taille avec un caillou supplémentaire, dans ce cas la transformation ajoute un troisième groupe de la taille des deux premiers et adjoint un deuxième caillou supplémentaire. On
va donc de temps en temps ajouter des cailloux, de temps en temps en retirer. Va-t-on s’arrêter ? La réponse est aujourd’hui inconnue [7].
Les mathématiques comme un jeu de cailloux [8] ?
Les mathématiques utilisent une méthode unique parmi les autres sciences. Tous les énoncés (les propositions, les théorèmes etc.) doivent être rigoureusement justifiés. Pour cela, il faut construire une « démonstration » qui consiste en une suite d’énoncés intermédiaires dont chacun est obtenu à partir des précédents en utilisant un certain nombre de « règles logiques » bien établies, du genre « si j’ai ceci alors j’ai ça » que j’enchaîne avec, par exemple, « si j’ai A et si j’ai B alors j’ai “A et B” ». Bien sûr, il faut bien partir de quelque part : ce sont des énoncés bien précis qu’on appelle les axiomes. On peut donc penser l’édifice mathématique comme un immense jeu, un peu comme un jeu d’échecs : il y a une position initiale (analogue aux axiomes), il y a des règles de mouvement des pièces (analogues aux règles de logique) et il s’agit de mouvoir les pièces (en respectant les règles !) pour aboutir à certaines positions (les théorèmes). Voici un jeu « mathématique » :
- Votre mission est de démontrer que tout nombre pair (autre que 2) est la somme de deux nombres premiers.
- Vous ne pourrez compter que sur les axiomes et les règles.
- À vous de naviguer pour arriver jusqu’au but.
- Bonne chance !
Ce jeu solitaire est beaucoup plus difficile que le jeu d’échecs !
Ceux qui ont déjà fait une démonstration mathématique ont déjà éprouvé cette insatisfaction devant une démonstration qui ne leur plaisait pas et qu’ils voulaient transformer, soit pour la rendre plus belle ou plus directe, soit pour éviter un argument qui leur semblait n’avoir rien à faire avec le théorème à démontrer. Vous avez trouvé avec beaucoup de peine l’échoppe que vous cherchiez dans le souk de Marrakech et vous voulez expliquer le chemin à un ami : il faut qu’il soit le plus simple possible et sans détour inutile. Est-ce possible ?
Une démonstration, avec sa suite d’énoncés intermédiaires, utiles ou inutiles, est similaire à nos rangées de petits cailloux, du premier au dernier, de l’axiome au théorème... Transformer une démonstration, pour en trouver une meilleure ressemble à transformer un alignement de petits cailloux. On voit donc que nos petits jeux de cailloux [9] ont une importance fondamentale en mathématiques, puisqu’ils décrivent la structure même de l’activité du mathématicien.
En fait, les logiciens ne considèrent pas seulement les démonstrations comme quelque chose qui sert aux mathématiciens, mais aussi comme un véritable objet mathématique au même titre que les nombres ou les figures géométriques. Les objets que manipulent les logiciens sont les démonstrations : ils sont donc amenés à faire des démonstrations à propos des démonstrations... Pourquoi pas ?
L’édifice des mathématiques est-il solide ?
Nous allons voir comment la terminaison peut garantir sa solidité.
On dit qu’une théorie est cohérente si on ne peut pas y démontrer tout et son contraire [10] ou ce qui revient au même si on ne peut pas y démontrer la proposition contradictoire (la proposition « faux »). Il est évidemment essentiel de démontrer que la logique est cohérente, sinon c’est tout l’édifice des mathématiques qui s’effondre.
On voit donc combien les petits cailloux sont importants !
Les calculs et l’indécidabilité de la terminaison
Pour définir une fonction ou une technique de simplification d’expressions, on utilise un procédé qui s’apparente à celui des petits cailloux [13], mais pour garantir que le programme ou la simplification est correct, il faut s’assurer que le procédé (ou le programme d’ordinateur), qui définit la fonction ou la simplification, s’arrête [14]. C’est tout simple ! Il suffit d’écrire un programme général qui prend comme donnée le programme dont on veut garantir la terminaison et qui teste si le dit programme termine ou non. Eh bien non, ça n’est pas si simple que ça, parce qu’Alan Turing a montré qu’un tel programme universel, qui teste la terminaison, n’existe pas. Cela a comme conséquence que pour chaque programme (ou chaque famille de programmes) il faudra inventer une méthode de terminaison ad hoc. Mais il restera des programmes pour lesquels toutes les méthodes ad hoc connues échouent lamentablement [15].
Des logiciels pour vérifier la terminaison
Comme tester la terminaison est assez subtil, nécessite des batteries de méthodes assez différentes les unes de autres et peut servir dans des programmes informatiques où la vie de personnes est en jeu [16], les scientifiques ont écrit des logiciels pour faire ce travail.
Une compétition
Comme les méthodes sont ad hoc, tous les logiciels n’ont pas le même comportement et on aimerait savoir quel est le meilleur logiciel. Par exemple on aimerait savoir si le logiciel de l’Université d’Orsay bat celui de l’Université d’Aix la Chapelle ou celui de l’Université d’Innsbrück ou celui de celle de Leipzig, d’Eindhoven ou de Nancy. Sans vouloir les positionner dans un ordre strict [17] on peut vouloir savoir sur quel type d’exemple tel ou tel logiciel est meilleur que tel autre. Pour départager tout le monde, des chercheurs ont eu l’idée de mettre sur pied une compétition où les logiciels de terminaison s’affronteraient sur des échantillons d’exemples bien choisis et renouvelés [18]. De cette compétition doivent sortir défis et améliorations.
Des démonstrations certifiées
Croire qu’un logiciel peut effectivement garantir la terminaison reste un acte de foi que tous ne veulent pas faire [19], aussi demande-t-on aujourd’hui aux logiciels de fournir un certificat, c’est-à-dire le terme d’une démonstration formelle qui peut être vérifiée par un outil adéquat indépendant [20] ou par un mathématicien courageux ! Aujourd’hui on peut espérer que plus personne ne mette en doute une démonstration de terminaison automatisée qui fournit un certificat.
Encore très active, la recherche sur la terminaison n’est pas près de s’arrêter.
Notes
[1] La réponse est oui, mais sa solution sortirait du cadre de cet exposé, une étude complète de ce type de réduction a été faite par A. Geser et H. Zantema.
[2] Le sens de « terminaison » utilisé ici est un emprunt de l’anglais, il signifie le fait qu’un processus s’arrête ou non.
[4] Il ne s’agit plus d’une petite main, mais d’une grosse main !
[5] En fait on teste la parité ou l’imparité, mais on a besoin de savoir la taille des paquets pour la reporter après transformation.
[6] non vides
[7] Ce problème est une présentation de la conjecture connue sous le nom de problème 3x+1, de problème de Collatz ou de problème de Syracuse qui est toujours non résolue à ce jour. Il s’appelle problème 3x+1 parce qu’il est souvent présenté sous la forme suivante : « prenez un nombre x, s’il est pair divisez le par 2, s’il est impair et n’est pas égal à 1 alors multipliez le par 3 et ajoutez 1 (autrement dit remplacez le par 3x+1), puis recommencez ».
[8] Notez que les mots calculs et cailloux ont la même origine
[9] et leurs petites sœurs les démonstrations !
[10] Autrement dit, on ne peut pas y démontrer A et non A.
[11] je dis « supposées », parce que dire qu’un théorème intermédiaire est « plus bas » qu’un autre est lié à la terminaison !
[12] Cela pourra faire l’objet d’un autre article.
[13] On dit qu’on définit une machine abstraite.
[14] La terminaison des programmes ou de ce qui leur ressemble s’appelle aussi la normalisation forte.
[15] C’est le cas de la fonction 3x+1.
[16] Imaginez un programme qui fait un certain nombre de tests avant d’activer le freinage d’une automobile.
[17] Les chercheurs savent bien qu’un ordre total n’est pas possible, comme ce serait folie de dresser un ordre total des universités !
[19] A commencer par l’auteur de cet article, qui ne croit pas plus le Sar Rabindranath Duval incarné par Pierre Dac.
[20] voyez le site du groupe de travail sur la terminaison certifiée
[21] La notion de base est rappelée dans l’article Et si les nombres pouvaient être infinis à gauche de la virgule plutôt qu’à droite...
[22] Je note les puissances par l’opérateur binaire ^, autrement dit 3^3 veut dire 3 fois 3 fois 3.
[23] car nous savons que 3^0 c’est 1 et que 3^1 ou 3^(3^0) c’est 3.
[24] que l’on appelle suite de Goodstein
[25] L. Kirby et J. Paris, « Accessible independence results for Peano arithmetic », dans Bull. London. Math. Soc., 14 (1982), 285-93
Partager cet article
Pour citer cet article :
Pierre Lescanne — «Est-ce que ça s’arrête ?» — Images des Mathématiques, CNRS, 2009
Laisser un commentaire
Actualités des maths
-
14 février 2019Bibliothèque Ibni Oumar Mahamat Saleh
-
14 février 2019Ingrid Daubechies et Claire Voisin reçoivent le prix L’Oréal-UNESCO
-
14 février 2019Les graphes, un autre univers en expansion (Paris, 20/2)
-
8 février 2019Pierre de Fermat : magistrat, philologue, mathématicien illustre mais énigmatique (Pechbusque, 14/2)
-
8 février 2019Cartographie en randonnée (Paris, 14/2)
-
5 février 2019Couleuvre au poing des probabilités (Villeurbanne, 11/2)
Commentaire sur l'article
Est-ce que ça s’arrête ?
le 8 octobre 2009 à 08:29, par Marc JAMBON