Ê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 GraphSearch.
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.
Publications associées (39)
Personnes associées (4)
Concepts associés (10)
Machine de Turing
En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.
Informatique quantique
L'informatique quantique est le sous-domaine de l'informatique qui traite des calculateurs quantiques et des associés. La notion s'oppose à celle d'informatique dite « classique » n'utilisant que des phénomènes de physique classique, notamment de l'électricité (exemple du transistor) ou de mécanique classique (exemple historique de la machine analytique). En effet, l'informatique quantique utilise également des phénomènes de la mécanique quantique, à savoir l'intrication quantique et la superposition.
Complexité en temps
En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Cours associés (6)
CS-251: Theory of computation
This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica
MATH-483: Gödel and recursivity
Gödel incompleteness theorems and mathematical foundations of computer science
MATH-642: Artificial Life
We will give an overview of the field of Artificial Life (Alife). We study questions such as emergence of complexity, self-reproduction, evolution, both through concrete models and through mathematica