Machine de Turing non déterministe

Alors que, connaissant le caractère lu sur le ruban et l'état courant, une machine de Turing déterministe dispose d'au plus une transition possible, une machine de Turing non déterministe peut en avoir plusieurs. En conséquence, tandis que les calculs d'une machine de Turing déterministe forment une suite, ceux d'une machine de Turing non déterministe forment un arbre, dans lequel chaque chemin correspond à une suite de calculs possibles.

On peut se représenter l'évolution d'une machine de Turing non déterministe ainsi : dans un état où il y a plusieurs transitions possibles, elle se duplique (triplique, etc.) et une sous-machine est créée pour chaque transition différente. Une machine de Turing non déterministe accepte une entrée s'il existe une séquence de choix (une branche de l'arbre, une sous-machine) qui atteint un état acceptant.

Une autre façon de se représenter les choix d'une machine de Turing non déterministe est de l'imaginer aussi chanceuse que possible : autrement dit, s'il existe une suite de choix qui aboutit à un état final acceptant, la machine fait cette suite de choix parmi les suites de choix de transitions possibles.

• ${\displaystyle Q}$ est un ensemble fini d'états.
• ${\displaystyle \Sigma }$, l'alphabet, est un ensemble fini de symboles.
• ${\displaystyle \iota \in Q}$ est l'état initial.
• ${\displaystyle \mathrm {\textvisiblespace} }$ est le symbole blanc(${\displaystyle \mathrm {\textvisiblespace} \in \Sigma }$)
• ${\displaystyle A\subseteq Q}$ est l'ensemble des états « acceptants », ou finaux.
• ${\displaystyle \delta :Q\backslash A\times \Sigma \rightarrow \left(Q\times \Sigma \times \{L,R\}\right)}$ est une relation binaire sur les états et les symboles. C'est la relation de transition. L est le décalage à gauche et R est le décalage à droite.

Une machine de Turing déterministe peut être décrite comme une machine de Turing non déterministe dont la relation de transition est fonctionnelle.

La notion d'acceptation de l'entrée est inchangée: une machine de Turing non déterministe accepte un mot en entrée si et seulement si quand la machine démarre sur une configuration où la tête est placée sur le premier caractère du mot sur le ruban blanc partout ailleurs, au moins une des séquences de calcul de la machine atteint un état acceptant ${\displaystyle \in A}$. La différence est qu'étant donnée une entrée, une machine déterministe n'a qu'une seule suite de configurations possible. La machine de Turing non déterministe en a plusieurs, ce qui signifie qu'elle peut accepter un mot tout en ayant plusieurs calculs non acceptants sur ce mot. C'est pourquoi la complémentarisation d'un langage est beaucoup plus coûteuse pour les machines non déterministes, il ne suffit pas d'inverser les états finaux et non finaux.

Le concept de machine de Turing non déterministe n'étend pas la notion de calculabilité. De ce fait, les machines de Turing non déterministes calculent exactement les mêmes fonctions que les machines de Turing déterministes, car une machine de Turing non déterministe peut être simulée par une machine de Turing déterministe. Toutefois la complexité des calculs diffère : la classe de complexité polynomiale qui leur est associée est la classe de complexité NP, qui contient la classe correspondante pour les machines de Turing déterministes. C'est pourquoi une dénomination de cette classe, à savoir NP, vient de leur nom et signifie Non deterministic Polynomial, autrement dit classe des problèmes pouvant être résolus en un temps polynomial par des machines de Turing non déterministes. On notera qu'on ne sait pas si cette classe NP est égale ou non à la classe P des problèmes pouvant être résolus en un temps polynomial par les machines de Turing déterministes : c'est le fameux problème P = NP.

• Machine de Turing
• Machine de Turing probabiliste
• Machine de Turing alternante
• Automate fini
• Théorie des langages
• Langage formel
• Théorie de la complexité des algorithmes