Loading AI tools
En informatique théorique, une machine de Turing symétrique est une machine de Turing dont le graphe des configurations est non-orienté, c'est-à-dire qu'il est possible de passer d'une configuration A à une configuration B, si et seulement si l'opération inverse est possible.
Une machine de Turing symétrique est une variante des machines de Turing classiques. Les transitions d'une machine de Turing symétrique sont de la forme (p,ab,D,cd,q), où p et q sont des états, a, b, c, d sont des lettres et D une direction de déplacement de la tête de lecture. Prenons par exemple D égual à droite, la transition (p,ab, D, cd, q) correspond à l'action décrite par la machine lorsque celle ci se trouve dans l'état p, a sa tête de lecture au-dessus de la lettre a, écrit c à la place de a, puis déplace sa tête de lecture d'une case vers la droite, au-dessus de la lettre b, écrit d à la place de b et passe dans l'état q. La transition inverse est aussi empruntable et vaut (q, cd, -D, ab, p). Le fait de changer les lettres deux par deux simplifie la définition mais n'est pas une nécessité.
Les machines de Turing symétriques ont été introduites en 1982 par Harry R. Lewis et Christos Papadimitriou[1],[2], en cherchant à classer plus finement le problème USTCON, consistant à déterminer s'il existe ou non un chemin entre deux sommets quelconques s et t dans un graphe non-orienté. Ce problème était alors connu comme appartenant à NL, sans avoir pourtant besoin du non-déterminisme de la classe NL.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
