Utilisateur:Alain Busser/Systèmes de tague
Un système de tague est un modèle de calculabilité défini par Emil Leon Post en 1943 comme système de réécriture. Ce modèle est Turing-complet: Toute fonction calculable peut être émulée par un système de tague de Post.
Définitions
modifierDéfinition d'un système de tague
modifierL'état (informatique) du système de tague est un mot de longueur variable, écrit dans un alphabet (en général de peu de lettres). 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 (de deux lettres 'a' et 'b' ou '0' et '1' pour le binaire, de trois lettres 'a', 'b' et 'c' pour l'exemple sur Collatz ci-dessous)
- un mot initial écrit dans l'alphabet
- des règles de réécriture définies par une fonction qui, à chaque lettre de l'alphabet, associe un suffixe écrit dans l'alphabet, qui sera ajouté à la fin du mot à chaque itération.
Un système de tague de paramètre m est parfois noté m-système. Les 2-systèmes sont les plus étudiés.
Fonctionnement du système de tague
modifierLe mot qui décrit l'état du système de tague évolue à instants discrets, appelés itérations, et à chaque itération, se passent successivement les choses suivantes:
- On regarde la première lettre du mot;
- on lui applique la règle de réécriture, qui lui associe un suffixe (puisque chaque lettre de l'alphabet est associée à un suffixe, et que la première lettre du mot est dans l'alphabet);
- on écrit ce suffixe à la fin du mot;
- on efface les m premières lettres du nouveau mot, y compris celle qui a déterminé le suffixe.
On arrête les itérations lorsque le mot est devenu vide, ou lorsque sa première lettre est la lettre de l'alphabet 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
modifierL'exemple suivant est un 3-système de tague qu'Emil Post affirmait avoir inventé en 1921; il s'écrit sur un alphabet de deux lettres a et b.
Règles de réécriture
modifier- 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
modifierAvec le mot initial aaaba, on a les étapes suivantes:
- 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;
- 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;
- 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;
- Le mot abaa commençant par a on lui ajoute aa pour avoir abaaaa puis aaa par suppression des 3 premières lettres;
- 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;
- 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.
- Lapremiè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
modifierPour faciliter la lecture de l'historique d'une 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
modifierDans 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
modifierDétermination de la parité
modifierVoici 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
modifierCe 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
modifierCe 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 n2 (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 + 12. Cette étape intermédiaire est omise dans le système de tague suivant, en définissant le successeur de n comme étant 3n + 12 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
modifierDans 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
modifierHao Wang a démontré en 1963 qu'un 2-système est Turing-complet; l'année suivante, c'est John Cocke, en collaboration avec Marvin Minsky, qui a démontré un résultat analogue (avec un 2-système aussi). Les deux ont simulé une machine de Turing universelle par un 2-système.
Systèmes cycliques
modifierDans 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
modifierNotes et références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Tag system » (voir la liste des auteurs).
- Cocke, J., Minsky, M.: "Universality of Tag Systems with P=2", J. Assoc. Comput. Mach. 11, 15–20, 1964.
- De Mol, L.: "Tag systems and Collatz-like functions", Theoretical Computer Science , 390:1, 92–101, January 2008. (Preprint N° 314.)
- Marvin Minsky 1961, Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines", the Annals of Mathematics, 2nd ser., Vol. 74, No. 3. (Nov., 1961), pp. 437–455. JSTOR:1970290.
- Marvin Minsky, 1967, Computation: Finite and Infinite Machines, Prentice–Hall, Inc. Englewoord Cliffs, N.J., no ISBN, Library of Congress Card Catalog number 67-12342.
- 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.
- Post, E.: "Formal reductions of the combinatorial decision problem", American Journal of Mathematics, 65 (2), 197–215 (1943). (les systèmes de tague sont introduits à partir de la page 203.)
- Rogozhin, Yu.: "Small Universal Turing Machines", Theoret. Comput. Sci. 168, 215–240, 1996.
- Wang, H.: "Tag Systems and Lag Systems", Math. Annalen 152, 65–74, 1963.
Liens externes
modifier- http://mathworld.wolfram.com/TagSystem.html
- http://mathworld.wolfram.com/CyclicTagSystem.html
- http://www.wolframscience.com/nksonline/page-95 (sur les systèmes cycliques)
- http://www.wolframscience.com/nksonline/page-669 (émulateur de systèmes de tague)
[[Catégorie:Informatique théorique]] [[Catégorie:Calculabilité]]