Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Système de tague
Résumé
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.
Source officielle
À propos de ce résultat
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.