Machine de Turing non déterministe

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.

Sommaire

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Machine de Turing non déterministe de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Machine De Turing Non Déterministe — Sommaire 1 Présentation intuitive 2 Description formelle 3 Résultat d une machine de Turing non déterministe 4 …   Wikipédia en Français

  • Machine de Turing non-déterministe — Sommaire 1 Présentation intuitive 2 Description formelle 3 Résultat d une machine de Turing non déterministe 4 …   Wikipédia en Français

  • Machine de Turing non deterministe — Machine de Turing non déterministe Sommaire 1 Présentation intuitive 2 Description formelle 3 Résultat d une machine de Turing non déterministe 4 …   Wikipédia en Français

  • Machine de turing non déterministe — Sommaire 1 Présentation intuitive 2 Description formelle 3 Résultat d une machine de Turing non déterministe 4 …   Wikipédia en Français

  • Machine De Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Machine de turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Machine de Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Automate fini non déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine …   Wikipédia en Français

  • Automate fini non déterministe généralisé — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine …   Wikipédia en Français

  • Oracle (machine de turing) — Pour les articles homonymes, voir Oracle et Turing (homonymie). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing. On peut les voir comme une machine de Turing… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”