Machine de Turing symétrique
# 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

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

Les machines de Turing symétriques ont été introduites en 1982 par Harry R. Lewis et Christos $Papadimitriou^,,$ 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.

