Machine de turing pdf

Un article de Wikipédia, l’encyclopédie libre. La machine machine de turing pdf également d’une table de transition, non représentée sur l’image.

Cette thèse n’est pas un énoncé mathématique, puisqu’elle ne suppose pas une définition précise des procédures algorithmiques. D’autre part, la personne doit mémoriser un état particulier parmi un ensemble fini d’états. Quoique son nom de « machine » puisse conduire à croire le contraire, une machine de Turing est un concept abstrait, c’est-à-dire un objet mathématique. Le ruban est supposé être de longueur infinie vers la gauche ou vers la droite, en d’autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution.

Si aucune action n’existe pour une combinaison donnée d’un symbole lu et d’un état courant, la machine s’arrête. Plusieurs définitions formelles proches les unes des autres peuvent être données d’une machine de Turing. L’une d’elles, relativement courante, est choisie ici. Le fonctionnement de la machine de Turing est alors le suivant. Ces deux informations permettent la mise à jour de l’état de la machine grâce à la fonction de transition.

La machine s’arrête lorsqu’elle rentre dans un état terminal. Le résultat du calcul est alors le mot inscrit sur le ruban. 1’ le plus à gauche. 0’ entre les deux séries. Par exemple, « 111 » devient « 1110111 ». Elle démarre son exécution dans l’état e1, remplace le premier 1 par un 0. 0 rencontré par un 1.