Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Machine de Turing non déterministe
Résumé
Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné.
Alors que, connaissant le caractère lu sur le ruban et l'état courant, une machine de Turing déterministe dispose d'au plus une transition possible, une machine de Turing non déterministe peut en avoir plusieurs.
En conséquence, tandis 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 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.
Une machine de Turing non déterministe accepte une entrée s'il existe une séquence de choix (une branche de l'arbre, une sous-machine) qui atteint un état acceptant.
Une autre façon de se représenter les choix d'une machine de Turing non déterministe est de l'imaginer aussi chanceuse que possible : autrement dit, s'il existe une suite de choix qui aboutit à un état final acceptant, la machine fait cette suite de choix parmi les suites de choix de transitions possibles.
est un ensemble fini d'états.
l'alphabet, est un ensemble fini de symboles.
est l'état initial.
est le symbole blanc()
est l'ensemble des états « acceptants », ou finaux.
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.
Une machine de Turing déterministe peut être décrite comme une machine de Turing non déterministe dont la relation de transition est fonctionnelle.
La notion d'acceptation de l'entrée est inchangée: une machine de Turing non déterministe accepte un mot en entrée si et seulement si quand la machine démarre sur une configuration où la tête est placée sur le premier caractère du mot sur le ruban blanc partout ailleurs, au moins une des séquences de calcul de la machine atteint un état acceptant .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.