Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Exemple : La machine de Turing qui suit possède un alphabet {‘0’, ‘1’}, ‘0’ éta

Exemple : La machine de Turing qui suit possède un alphabet {‘0’, ‘1’}, ‘0’ étant le « blanc ». On suppose que le ruban contient une série de ‘1’, et que la tête de lecture/écriture se trouve initialement au-dessus du ‘1’ le plus à gauche. Cette machine a pour effet de doubler le nombre de ‘1’, en intercalant un ‘0’ entre les deux séries. Par exemple, « 111 » devient « 1110111 ». L’ensemble d’états possibles de la machine est {e1, e2, e3, e4, e5} et l’état initial est e1. La table d’actions est la suivante : Exemple de table de transition Ancien état Symbole lu Symbole écrit Mouvement Nouvel état e1 0 (Arrêt) 1 0 Droite e2 e2 1 1 Droite e2 0 0 Droite e3 e3 1 1 Droite e3 0 1 Gauche e4 e4 1 1 Gauche e4 0 0 Gauche e5 e5 1 1 Gauche e5 0 1 Droite e1 L’exécution de cette machine pour une série de deux '1' serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et rouges) : Exécution (1) Exécution (2) Exécution (3) Exécution (4) Étape État Ruban 1 e1 11 2 e2 01 3 e2 010 4 e3 0100 Étape État Ruban 5 e4 0101 6 e5 0101 7 e5 0101 8 e1 1101 Étape État Ruban 9 e2 1001 10 e3 1001 11 e3 10010 12 e4 10011 Étape État Ruban 13 e4 10011 14 e5 10011 15 e1 11011 (Arrêt) Le comportement de cette machine peut être décrit comme une boucle :  Elle démarre son exécution dans l’état e1, remplace le premier 1 par un 0.  Puis elle utilise l’état e2 pour se déplacer vers la droite, en sautant les 1 (un seul dans cet exemple) jusqu'à rencontrer un 0 (ou un blanc), et passer dans l'état e3.  L’état e3 est alors utilisé pour sauter la séquence suivante de 1 (initialement aucun) et remplacer le premier 0 rencontré par un 1.  L'état e4 permet de revenir vers la gauche jusqu’à trouver un 0, et passer dans l’état e5.  L'état e5 permet ensuite à nouveau de se déplacer vers la gauche jusqu’à trouver un 0, écrit au départ par l’état e1.  La machine remplace alors ce 0 par un 1, se déplace d’une case vers la droite et passe à nouveau dans l’état e1 pour une nouvelle itération de la boucle. Ce processus se répète jusqu’à ce que e1 tombe sur un 0 (c’est le 0 du milieu entre les deux séquences de 1) ; à ce moment, la machine s’arrête. Dans l'exemple qui suit, la machine de Turing possède un ruban vide et permet de créer le nombre 01010101010101... Exemple de table infinie Ancien état Symbole écrit Mouvement Nouvel état a 0 Droite b b 1 Droite a L’exécution de cette machine serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et magenta) : Exécution de la Machine infinie Etape Etat Ruban 1 a 0 2 b 01 3 a 010 4 b 0101 5 a 01010 6 b 010101 7 a 0101010 8 b 01010101 ... ... 01010101... Le comportement de cette machine peut être décrit comme une boucle infinie :  Elle démarre son exécution dans l’état a, ajoute un 0 et se déplace à droite.  Puis elle passe à l'état b, ajoute un 1 et se déplace à droite.  Elle revient dans l'état a et réitère la première étape. Ainsi cette machine permet de créer le nombre 010101010101... uploads/Industriel/ machine-de-turing.pdf