Système de tague

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, plus précisément en calculabilité, un système de tague (tag system en anglais) est un modèle de calculabilité défini par Emil Leon Post en 1943 comme système de réécriture. C'est un cas particulier de système de Post. Ce modèle est Turing-complet : toute fonction calculable peut être émulée[Quoi ?] par un système de tague de Post.

Définitions[modifier | modifier le code]

Définition d'un système de tague[modifier | modifier le code]

Un système de tague est défini par :

  • un entier naturel m (nombre de lettres du préfixe, à effacer après chaque itération) ;
  • un alphabet fini A ;
  • un mot initial écrit avec l'alphabet A;
  • une règle de réécriture par lettre de l'alphabet  : à toute lettre a, on associe un mot P(a).

Un système de tague de paramètre m est appelé m-système. Les 2-systèmes sont les plus étudiés[pourquoi ?].

Fonctionnement du système de tague[modifier | modifier le code]

On transforme un mot de la façon suivante :

  • on regarde la première lettre a du mot ;
  • on ajoute P(a) à la fin du mot ;
  • on efface les m premières lettres.

Le fonctionnement du système de tague consiste à démarrer avec le mot initial puis à appliquer des transformations. On arrête les itérations lorsque le mot est de longueur plus petite que m. Il existe des variantes de système de tague où les itérations s'arrête si le mot est vide, ou si sa première lettre est une lettre spéciale qui code l'arrêt (typiquement « H » comme « halt »). Il y a des systèmes de tague qui ne terminent jamais parce que la longueur du mot est globalement croissante ; dans ce cas, chaque fois que le mot a une forme particulière (par exemple, si son écriture ne comprend que des lettres a), il représente (par exemple par le nombre de a) un terme d'une suite (mathématiques).

Exemple[modifier | modifier le code]

L'exemple suivant est un 3-système de tague qu'Emil Post affirmait[réf. nécessaire] avoir inventé en 1921 ; il s'écrit sur un alphabet de deux lettres a et b.

Règles de réécriture[modifier | modifier le code]

  • Si la première lettre est a, le suffixe sera aa
  • Si la première lettre est b, le suffixe sera bbab

Simulation pas par pas[modifier | modifier le code]

Avec le mot initial aaaba, on a les étapes suivantes :

  1. Le mot aaaba commençant par un a on lui rajoute le suffixe aa pour avoir aaabaaa puis baaa après avoir enlevé les 3 premières lettres ;
  2. Le mot baaa commençant par b, on lui rajoute le suffixe bbab pour avoir baaabbab puis abbab par suppression des 3 premières lettres ;
  3. Le mot abbab commençant par a on lui ajoute le suffixe aa pour avoir abbabaa puis abaa par suppression des 3 premières lettres ;
  4. Le mot abaa commençant par a on lui ajoute aa pour avoir abaaaa puis aaa par suppression des 3 premières lettres ;
  5. Le mot aaa commençant par a on lui ajoute là encore le suffixe aa pour avoir aaaaa puis, par suppression des 3 premières lettres, aa ;
  6. Le mot aa commençant par a, là encore le suffixe sera aa et on obtiendra le mot aaaa puis, par suppression des 3 premiers a, le mot d'une seule lettre a ;
  7. La première lettre de a est a, donc on lui rajoute le suffixe aa pour avoir aaa, mot de trois lettres qui se vide lorsqu'on supprime ses 3 (premières) lettres.

Le mot étant vide, le système a atteint le point d'arrêt et l'exécution se termine là.

Notation[modifier | modifier le code]

Pour faciliter la lecture de l'historique d'un système de tague, on écrit les mots non en dessous l'un de l'autre, mais décalés, ici de 3 lettres, vers la droite, afin que les lettres identiques soient alignées verticalement. L'exemple précédent donne ceci :

3-système de tague (Post)
    Alphabet : {a,b} 
    Règles de transformation :
         a  -->  aa
         b  -->  bbab

Calcul
    Mot initial : aaaba
                     baaa  
                        abbab
                           abaa
                              aaa
                                 aa
                                    a
                                     (arrêt)

Origine du nom[modifier | modifier le code]

Dans son article de 1943, Post parle de simuler un tel système de réécriture par une machine de Turing à deux têtes, l'une qui lit et l'autre qui écrit. Les deux têtes ne reculent jamais, mais alors que la tête qui lit avance toujours de m cases, celle qui écrit avance d'une longueur variable puisque dépendant du suffixe. Le mouvement des deux têtes évoquait à Post celui de deux enfants jouant à « attrape », jeu dont le nom québécois est tague. Le fait qu'on puisse comparer l'ajout du suffixe à un tag est donc une coïncidence.

Exemples[modifier | modifier le code]

Détermination de la parité[modifier | modifier le code]

Voici un 2-système calculant la parité du nombre initial de o dans un mot ne comprenant presque que des o ; par exemple, le mot oooooPI (comprenant 5 fois la lettre o) aboutit, lors de l'arrêt, au mot impair :

calcul de parité
    Alphabet : {o,I,P,a,i,m,p,r} 
    Règles de transformation :
         o  -->  (mot vide)
         I  -->  Iimpair
         P  -->  pair
         a  -->  (arrêt)
         i  -->  (arrêt)
         m  -->  (arrêt)
         p  -->  (arrêt)
         r  -->  (arrêt)


Calcul
    Mot initial : oooooPI
                    oooPI  
                      oPI
                        I
                          impair
                            (arrêt)

Triplement[modifier | modifier le code]

Ce 1-système triple le nombre de o dans un mot :

1-système de triplement
    Alphabet : {o,H} 
    Règles de transformation :
         o  -->  ooo
         H  -->  (arrêt)


Calcul
    Mot initial : oooH
                   ooHooo  
                    oHoooooo
                     Hooooooooo
                            (arrêt)

Cette variante donne les puissances de 3 : chaque fois que le mot commence par T, il contient un nombre de o qui est successivement 1, 3, 9, 27, etc. :

Suite géométrique de raison 3
    Alphabet : {o,T} 
    Règles de transformation :
         o  -->  ooo
         T  -->  T


Calcul
    Mot initial : To <--> 1
                   oT 
                    Tooo <--> 3
                     oooT
                      ooTooo
                       oToooooo
                        Tooooooooo <-> 9
                         oooooooooT
                          ooooooooTooo
                           oooooooToooooo
                            ooooooTooooooooo
                             oooooToooooooooooo
                              ooooTooooooooooooooo
                               oooToooooooooooooooooo
                                ooTooooooooooooooooooooo
                                 oToooooooooooooooooooooooo
                                  Tooooooooooooooooooooooooooo <--> 27
                                        etc


Calcul d'une suite de Collatz[modifier | modifier le code]

Ce 2-système de tague vient de [De Mol, 2008]. Il n'a pas de symbole d'arrêt mais s'arrête tout seul sur tout mot de moins de 2 lettres, et calcule la suite de Collatz.

Dans la suite originelle de Collatz, le successeur de n est ou bien n/2 (pour n pair), ou bien 3n + 1 (pour n impair). Le nombre 3n + 1 étant pair pour n impair, le terme de la suite qui suit 3n + 1 est donc 3n + 1/2. Cette étape intermédiaire est omise dans le système de tague suivant, en définissant le successeur de n comme étant 3n + 1/2 pour n impair.

Dans ce système de tague, un entier naturel n est représenté par le mot aa...a avec n fois la lettre a.

2-système de tague (de Mol)
    Alphabet : {a,b,c} 
    Règles de transformation :
         a  -->  bc
         b  -->  a
         c  -->  aaa

Calcul
    Mot initial : aaa <--> n=3
                     abc  
                       cbc
                         caaa
                           aaaaa  <--> 5
                             aaabc
                               abcbc
                                 cbcbc
                                   cbcaaa
                                     caaaaaa
                                       aaaaaaaa  <--> 8
                                         aaaaaabc
                                           aaaabcbc
                                             aabcbcbc
                                               bcbcbcbc
                                                 bcbcbca
                                                   bcbcaa
                                                     bcaaa
                                                       aaaa  <--> 4
                                                         aabc
                                                           bcbc
                                                             bca
                                                               aa  <--> 2
                                                                 bc
                                                                   a  <--> 1
                                                                    (arrêt)

Problème du 3-système de Post[modifier | modifier le code]

Dans son article de 1943, Post décrit le 3-système présenté en exemple au début de cet article (aa,bbab) noté (00,1101) comme difficile. Il dit que même si chaque fois qu'il y a un a au début le mot raccourcit d'une lettre, soit autant qu'il s'allonge lorsque sa première lettre est b, il ne semble pas y avoir de lien simple entre le pourcentage de a dans le mot initial, et le fait qu'on puisse aboutir à un mot vide. En 1967, Minsky propose d'essayer avec le mot baabaabaabaabaabaabaa qui donne un système semblant s'allonger sans limite. Des systèmes à caractère périodique peuvent aussi exister :

3-système de tague (Post)
    Alphabet : {a,b} 
    Règles de transformation :
         a  -->  aa
         b  -->  bbab

Calcul
    Mot initial : babaa
                     aabbab  
                        babaa
                           aabbab
                              babaa
                                 aabbab
                                   (etc.)

Turing-complétude[modifier | modifier le code]

Hao Wang a démontré en 1963 qu'un 2-système est Turing-complet[1] ; l'année suivante, John Cocke et Marvin Minsky démontre un résultat analogue (avec un 2-système aussi)[2]. Ils simulent une machine de Turing universelle par un 2-système.

Systèmes cycliques[modifier | modifier le code]

Dans un système cyclique, les suffixes ne dépendent pas de la première lettre mais sont choisis cycliquement dans une liste de mots. Cette généralisation a été créée par Matthew Cook dans la démonstration du caractère Turing-complet de l'automate cellulaire dit règle 110.


Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (en) Hao Wang, « Tag systems and lag systems », Mathematische Annalen, vol. 152, no 1,‎ , p. 65–74 (ISSN 0025-5831 et 1432-1807, DOI 10.1007/BF01343730, lire en ligne)
  2. John Cocke et Marvin Minsky, « Universality of Tag Systems with P = 2 », J. ACM, vol. 11, no 1,‎ , p. 15–20 (ISSN 0004-5411, DOI 10.1145/321203.321206, lire en ligne)

Autres :

  • Alan Cobham, « Uniform tag sequences », Mathematical Systems Theory, vol. 6, no 1-2,‎ , p. 164–192 (DOI 10.1007/BF01706087, Math Reviews 0457011).
  • John Cocke et Marvin Minsky, « Universality of Tag Systems with P=2 », Journal of the ACM, vol. 11, no 1,‎ , p. 15–20 (DOI 10.1145/321203.321206).
  • Liesbeth De Mol, « Tag systems and Collatz-like functions », Theoretical Computer Science, vol. 390, no 1,‎ , p. 92–101 (DOI 10.1016/j.tcs.2007.10.020, lire en ligne).
  • Marvin Minsky, « Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines », The Annals of Mathematics, 2e série, vol. 74, no 3,‎ , p. 437-455 (JSTOR 1970290, lire en ligne).
  • Marvin Minsky, Computation: Finite and Infinite Machines, Englewoord Cliffs, N.J., Prentice–Hall, coll. « Prentice-Hall series in automatic computation », , xvii+317 p. (LCCN 67-12342, SUDOC 015222489)
    Dans le chapitre 14 titré « Very Simple Bases for Computability », la sous-section 14.6 « The Problem of “Tag” and Monogenic Canonical Systems » (pp. 267–273) est consacrée aux systèmes de Post et particulièrement le (00, 1101) vu ci-dessus : « Post found this (00, 1101) problem “intractable,” and so did I, even with the help of a computer. » Il évoque également la théorie de Cocke.
  • Emil Post, « Formal reductions of the combinatorial decision problem », American Journal of Mathematics, vol. 65, no 2,‎ , p. 197-215 — Les systèmes de tague sont introduits à partir de la page 203.
  • Yurii Rogozhin, « Small universal Turing machines », Theoretical Computer Science, vol. 168, no 2,‎ , p. 215-240 (DOI 10.1016/S0304-3975(96)00077-1).
  • Hao Wang, « Tag systems and lag systems », Mathematische Annalen, vol. 152, no 1,‎ , p. 65-74 (DOI 10.1007/BF01343730).

Liens externes[modifier | modifier le code]