Machine de Turing non déterministe

Une machine de Turing non-déterministe ressemble à une machine de Turing habituelle, c'est-à-dire déterministe, mais elle diffère d'elle en ce qu'elle peut avoir, pour un état donné, plusieurs transitions activables.

Présentation intuitive

Alors que, connaissant le caractère lu sur le ruban et l'état courant, une machine de Turing (habituelle, c'est-à-dire déterministe) a au plus une transition possible, une machine de Turing non déterministe peut en avoir plusieurs. Cela signifie qu'alors 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 s'imaginer 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 chaque sous-machine ainsi créée active une transition différente.

Description formelle

• Q est un ensemble fini d'états.
• Σ, 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.

Lien avec les machines de Turing déterministes

L'introduction du 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, en termes de complexité des calculs les choses changent. 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.

Voir aussi

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