Machine de Turing non déterministe

Une machine de Turing non déterministe est un modèle abstrait de machine ou il y a plusieurs possibilité par transition. On montre cependant ce que modèles est équivalent à une machine de Turing.

Définition

Cette machine se distingue de la machine de Turing normale parce que la fonction de transition rend un sous ensemble fini de $Q \times \{0, 1\} \times \{\leftarrow, \rightarrow\}$ et non juste un nouvel état, un nouveau caractère et une direction : elle donne plusieurs possibilités. Une machine de Turing normale est un cas particulier de machine de Turing non déterministe. C'est la machine elle même qui fait les choix pour arriver, si c'est possible à un choix de 1. Si aucun choix ne fait arriver à 1, il est possible que parfois elle s'arrête sur 0 et parfois ne s'arrête pas.

Prenons par exemple la machine de Turing non déterministe suivante :

• $\delta(\text{START}, 0) = \{(\text{START}, 1, \leftarrow), (\text{START}, 0, \rightarrow)\}$
• $\delta(\text{START}, 1) = \{(\text{STOP}, 1, \rightarrow) \}$

Avec l'entrée $E=01$ Il y a plein de choix possible :

1. On peut par exemple s'arrêter sur un 0 :
   1. de $\delta(\text{START}, 0)$ on choisit $(\text{START}, 0, \rightarrow)$
   2. puis de $(\text{START}, 1)$ choisir la seule possibilité $(\text{STOP}, 1, \rightarrow)$
2. On peut aussi s'arrêter sur un 1 :
   1. de $\delta(\text{START}, 0)$ on choisit $(\text{START}, 1, \leftarrow)$
   2. puis de de $\delta(\text{START}, 0)$ on choisit $(\text{START}, 0, \rightarrow)$
   3. enfin de $(\text{START}, 1)$ choisir la seule possibilité $(\text{STOP}, 1, \rightarrow)$

Donc la sortie de $M(01) = 1$

Avec une entrée vide en revanche, tous les choix mènent à une sortie en 0 ou une boucle infinie (faites le test) et donc $M()$ n'est pas déterminé.

Pour rendre notre machine de Turing déterministe précédente polynomiale, il faut lui interdire d'avoir des transitions infinies. Par exemple ne pas refaire boucler sur $\text{START}$. :

• $\delta(\text{START}, 0) = \{(\text{UN}, 1, \leftarrow), (\text{UN}, 0, \rightarrow)\}$
• $\delta(\text{START}, 1) = \{(\text{STOP}, 1, \rightarrow) \}$
• $\delta(\text{UN}, 1) = \{(\text{STOP}, 1, \rightarrow) \}$
• $\delta(\text{UN}, 0) = \{(\text{STOP}, 0, \rightarrow) \}$

De là toutes les entrées vont forcément s'arrêter. On a toujours $M(01) = 1$, mais maintenant $M() = 0$.

Usage

Ce qui nous intéresse ici ce n'est plus l'exécution effective d'une telle machine mais s'il existe pour une entrée donnée, une suite de transitions emmenant à l'état final. C'est à dire qu'il existe une suite de nombres $(t_1, \dots, t_k)$ telle que à chaque instruction $i$ on ait pu choisir le $t_i$ème choix pour que la $k$ instruction mène à un état final.

En représentant les choix sous la forme d'un arbre, on peut représenter $\delta$ comme ça :

Une exécution de la machine revient à suivre un chemin dans cet arbre, donc qu'à partir de l'état initial $e$ et du caractère $a$ sous le curseur, on a :

• $(e_{t_1}, a_{t_1}, f_{t_1}) \in \delta(e, a)$
• $(e_{t_1\dots t_i}, a_{t_1\dots t_i}, f_{t_1\dots t_i}) \in \delta(e_{t_1t_2\dots t_{i-1}}, a_{t_1t_2\dots t_1i-1})$

Exemple

Prenons la machine non déterministe suivante :

Équivalence avec une machine de Turing

La machine de Turing non déterministe est un outil théorique très puissant car il permet de démontrer simplement beaucoup de théorèmes d'informatique théorique. Cependant, elle ne permet pas de faire plus de chose qu'une machine normale.

k = 1

Tant que Vrai:
  on construit un tableau T contenant tous les mots de $Q$ de longueur $k$ (il y en a $2^k$)
  pour chaque élément e de T:
    exécuter M en suivant, si possible les éléments de e dans l'ordre lorsqu'il y a un choix.
    Si l'exécution de M est possible et se termine sur un 1:
      rendre 1
  Si toutes les executions de T se sont terminées:
    rendre 0
  k = k+1

Notez que dans la preuve précédente on a bien besoin que la machine s'arrête sur toute entrée, sinon notre machine déterministe ne s’arrêterait jamais s'il existait une suite de choix pouvant mener à une exécution infinie.

Comme la machine de Turing non déterministe est polynomiale on a de plus :

La machine de Turing non déterministe n'est qu'une façon plus simple de décrire les mêmes choses. Dans notre cas, cela va unifier la définition des classes $P$ et $NP$. En effet :

Si on rend déterministe la machine non déterministe exemple, on voit qu ele non déterministe permet de simuler une boucle tant que non 101 avancer de 1 case vers la droite : le non-déterminisme est une façon de condenser une énumération de choix.