Machine de Turing non-déterministe

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant.

Sommaire

1 Présentation intuitive
2 Description formelle
3 Résultat d'une machine de Turing non-déterministe
4 Voir aussi

[modifier] Présentation intuitive

Alors qu'une machine de Turing normale (déterministe), connaissant le caractère lu sur le ruban et l'état courant, a au plus un choix pour passer dans l'état suivant, une machine de Turing non-déterministe en a plusieurs.

Ce qui signifie qu'alors qu'une machine de Turing déterministe effectue une série de calculs, une machine de Turing non-déterministe effectue un arbre de calculs, chaque chemin de cet arbre correspondant à une série de calculs possibles.

On peut imaginer qu'une machine de Turing non-déterministe arrivée à un état où il y a plusieurs états suivants possible, se divise, elle-même et son ruban, et que chaque sous-machine va dans un état différent.

Cette description permet facilement de voir qu'une vraie machine de Turing non-déterministe, qui peut effectuer un nombre illimité de calculs en parallèle en autant de temps qu'il en faudrait pour résoudre un seul calcul n'est pas constructible dans le monde réel (nous ne pouvons construire que des machines de Turing déterministes). La machine de Turing non-déterministe est donc un outil théorique. Il est toutefois possible de construire des machines qui, face à plusieurs possibilités de choisir l'état suivant, en choisissent un arbitrairement. Nous obtenons ainsi une machine qui donne un seul résultat à la fois, mais ce ne sera pas forcément toujours le même si on exécute le traitement plusieurs fois à la suite.

[modifier] Description formelle

$Q$ est un ensemble fini d'états.
$Σ$ est l'alphabet, un ensemble fini de symboles.
$\iota \in Q$ est l'état initial.
$\sqcup$ est le symbole blanc( $\sqcup \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 fonction multivalué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.