Machine de Turing non déterministe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné.

Présentation[modifier | modifier le code]

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 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. On dit de la machine de Turing non déterministe qu'elle 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 de la machine de Turing non déterministe est de l'imaginer aussi chanceuse que possible: s'il existe un choix qui aboutit à un état acceptant, elle fait ce choix parmi les transitions possibles.

Description formelle[modifier | modifier le code]

  • est un ensemble fini d'états.
  • , l'alphabet, est un ensemble fini de symboles.
  • est l'état initial.
  • est le symbole blanc()
  • est l'ensemble des états « acceptants », ou finaux.
  • 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-deterministe 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 . (Pour les machines de Turing déterministes, les séquences de calculs sont les préfixes d'une unique séquence potentiellement infinie, ce n'est pas le cas dans les machines non déterministes.)[pas clair]

Impact sur le temps de calcul[modifier | modifier le code]

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.

Articles connexes[modifier | modifier le code]