Machine de Turing symétrique

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.