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 une machine de Turing habituelle, c'est-à-dire déterministe, mais qui 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 est déterministe en ayant 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.

Description formelle[modifier | modifier le code]

  • Q est un ensemble fini d'états.
  • \Sigma, l'alphabet, est un ensemble fini de symboles.
  • \iota \in Q est l'état initial.
  • \textvisiblespace est le symbole blanc(\textvisiblespace \in \Sigma)
  • A \subseteq Q est l'ensemble des états « acceptants », ou finaux.
  • \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.

Dans une machine de Turing ordinaire, la relation de transition est fonctionnelle.

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é et ainsi 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]