21/05/2007

Non Deterministic Turing Machine

Non Deterministic Turing Machine

Une machine de Turing non déterministe est une machine de Turing qui, de manière analogue aux automates finis non déterministes, peut pour n'importe quel état dans lequel elle se trouve et pour n'importe quel symbole lu prendre n'importe quel action plutôt qu'une unique prédéterminée. On sous entend par action le fait d'écrire un symbole sur la bande, déplacer la tête de lecture et changer d'état. La sélection de l'action à effectuer se fait sans suivre de règleprédéterminée.
Par exemple prenons le langage L = {ww: w { a , b }* }. Considérant une chaîne x, une NTM acceptant le langage L devinerait le milieu de x, cad le point de départ de la 2ème partie de x. Ensuite elle effectuerait comparaison de la première partie de x avec la seconde en prenant le i-eme symbol de chacune des parties. Une machine de Turing déterministe, d'un autre coté, ne peut pas deviner le milieu de x. Elle doit le trouver en dissociant les symboles des extrémités.

On peut prouver qu'une NTM (Non deterministic Turing Machine) est juste aussi puissante qu'une DTM (Deterministic Turing Machine).

De manière intuitive on pourrait penser qu'une NTM est plus puissante qu'une DTM, notamment a cause du fait qu'elles peuvent exécuter de multiples actions en même temps et qu'une seule d'entre elles ait besoin d'aboutir. Mais n'importe quel langage reconnu par un NTM peut être reconnu par une DTM: elle peut simuler chacun des transitions de la NTM en faisant des copies de l'état simulé quand plusieurs transitions sont possibles. Ainsi la DTM peut simuler la parallélisation des états de manière similaire à un système d'exploitation multitache.
Néanmoins le temps supplémentaire nécessaire à cette "simulation" n'est pas généralement connu et s'apparente au problème "P=NP" pour lequel nous vous invitons a consulter le rapport de nos camarades.

Définition

De manière formelle, une machine de Turing non déterministe est un sextuplé , où

• Q est un ensemble fini d'états
• Σ est un ensemble fini de symboles (l'alphabet de la bande)
• est l'état initial.
• est le symbole blanc ()
• est l'ensemble des états "acceptants", ou finaux.
• est une fonction multi-valuée sur les états et les symboles. C'est la fonction de transition. L est le décalage à gauche et R est le décalage à droite.

  Dans une machine de Turing ordinaire, la fonction de transition n'est pas multi-valuée.

 

On peut noter certaines représentations où l'état initial est remplacé par un ensemble d'états. Il est évident que ceci est équivalent à commencer par un unique état qui ensuite continue sur de multiples états (en l'occurrence ceux de l'ensemble précédemment cité).
Une variante inclus aussi un ensemble d'états dits "de rejet". Une NTM "rejette" si tous les chemins calculés mènent à des états de rejet.

Non-determinisme Borné

Une NTM est dite bornée si elle s'arrête au bout d'un certain nombre d'actions et à ainsi un nombre possible de configurations borné.

NTMs et Ordinateurs Quantiques

Il est souvent sous entendu à tord que les ordinateurs quantiques sont des NTMs. Ceci peut être réfuté par le fait que les ordinateurs quantiques ne peuvent résoudre des problèmes de type "NP-Complets"