Syracuse reformulé

Peut-être vous êtes vous déjà amusés avec le célèbre problème «3n+1» appelé aussi conjecture de Syracuse (ou de Collatz) pour d'obscures raisons.

Le principe est de transformer un entier n en n/2 si celui-ci était pair et en 3n+1 si il était impair. La question est alors simple : Est-ce que toute itération de ce procédé conduit inexorablement au cycle 1-4-2 ?

À ce jour, la question reste ouverte bien que de nombreux résultats existent (longueur minimale d'un éventuel cycle, résultats probabilistes…)

En fait on peut voir le problème de Syracuse comme un système de réécriture de termes (en gros c'est une grammaire formelle dont les règles peuvent contenir des schémas).

Pour cela, il faut avant tout coder les entiers, nous allons donc utiliser le meilleur codage qui soit : le codage par bâtons !
On considère un symbole 0 de constante et un symbole S (pour successeur) de fonction d'arité 1. L'entier n est alors codé par S…S0 où S est itéré n fois.
Mais on sera amené à considérer le double ou le triple d'un nombre, il faut donc deux nouveaux symboles : D (pour double) et T (pour triple) qui satisfont les équations :

• DSx ~ SSDx     c'est-à-dire    2(x+1) = 2x+1+1  
• TSx ~ SSSTx 

 (pour des raisons qui seront claires plus tard, la première équations sera utilisée dans le sens réciproque et la seconde dans le sens direct)

Enfin pour encadrer le codage de l'entier et pouvoir appliquer les règles, on a besoin d'un symbole-le-plus-à-gauche noté L, également d'arité 1.

Reste à traduire les règles du jeu (Syracuse) :

• Si le nombre est pair, c'est-à-dire de la forme 2x, alors on peut dériver x ce qui donne :
  LDx → Lx
• Si un nombre est impair, c'est-à-dire de la forme 2x+1, alors on peut dériver 3(2x+1)+1 ce qui donne :
  LSDx → LSTSDx

À partir de là, il faut se rappeler que notre but est de simplifier le plus possible l'expression (pour arriver peut-être à LS0), il faut donc éliminer les D et T. On a déjà une règle d'élimination des D, c'est pour cela qu'il faudra les faire remonter vers la gauche. Et on ajoute alors :

• Règle d'élimination des T : T0 → 0
• Règle d'introduction des D (il faut bien qu'ils apparaissent quelque-part et qu'on les fasse remonter pour qu'on puisse exprimer notre nombre sous la forme 2n ou 2n+1)  : 0 → D0
• Commutativité : TDx → DTx

 L'enchaînement de ces chaînes de caractères au cours des itérations de la fonction de Syracuse (S = Gris, D = Vert, T = Rouge).

Cette vision permet d'illustrer un théorème (qui fait l'objet d'un développement d'agrégation, cf [Baader-Nipkow]) qui stipule que la terminaison d'un système de réécriture est indécidable. En effet dans le cas contraire on saurait depuis longtemps ce qu'il en est des suites de Syracuse.

C'est fonctionnel donc ça marche !

(cliquez pour agrandir)

Graphe représentant les espaces fonctionnels usuels. Je peaufine celui-là depuis un certain temps déjà sans jamais me décider (doit-on faire apparaître les espaces de Sobolev ? Les espaces de Lebesgue "loc" ?) ou encore pour corriger à chaque fois des erreurs (L'espace de Schwarz n'as pas de produit de convolution interne, par contre on peut convoler n'importe quelle distribution avec un distribution à support compact).

Enfin j'ai vainement essayé de faire apparaître la dualité à la manière d'un miroir, mais cette vision a ses limites (le bidual n'est plus ce qu'il était).

Des graphes similaires et plus complets (bien que pas en couleur…) sont présent dans Dunford & Schwartz, Linear Operator I & II