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 représentée par un système de tague de Post.
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.
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êtent 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).
L'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.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
vignette|L'animation illustre une machine impossible : il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.
En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-complete) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n'importe quelle machine de Turing. Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité.
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 représentée par un système de tague de Post. 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).