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.