Machine de Turing symétrique
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.
Définition modifier
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é.
Intérêt modifier
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.
Références modifier
- Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms. Manuscript. 1998.
- Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science. p. 161-187. 1982.
