Remerciez-le!

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Définition Machine de Turing . . . ∗ ∗ ∗ 1 1 1 . . . Ruban entrée/sortie q0 Instructions de Base 1. Ecrire 1 dans la zone du ruban pointée par la tête de lecture-écriture si cette zone était vide (ou contient ⋆) au paravant 2. Ecrire ⋆dans dans la zone du ruban pointée par la tête de lecture-écriture si celle-ci contenait 1. 3. Se déplacer à droite (r) pour pointer la zone du ruban qui suit la zone pointée. 4. Se déplacer à gauche (l) pour pointer la zone du ruban qui suit immédiatement la zone pointée. 5. Stopper (s) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . La machine r : fait avancer d’une case à droite Sous forme d’instructions d’un programme: q1 ⋆ r q2 q1 1 r q2 q2 ⋆ s q2 q2 1 s q2 Sous forme d’automate: q1 start q2 *,r 1,r s s r: Machine de Turing se déplace à droite d’une case et s’arrête. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . La machine l : fait avancer d’une case à gauche Sous forme d’instructions d’un programme: q1 ⋆ l q2 q1 1 l q2 q2 ⋆ s q2 q2 1 s q2 Sous forme d’automate: q1 start q2 *,l 1,l s s l: Machine de Turing se déplace à gauche d’une case et s’arrête. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . La machine de Turing qui imprime 1 Sous forme d’instructions d’un programme: q1 ⋆ 1 q2 q1 1 1 q2 q2 ⋆ s q2 q2 1 s q2 Sous forme d’automate: q1 start q2 *,1 1,1 *,s 1, s I : Machine de Turing qui imprime 1 et s’arrête. A l’état q1 si la tête de lecture/écriture pointe une case vide alors elle écrit 1 et passe à l’état q2 et stoppe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . La machine de Turing qui efface (imprime ∗) Sous forme d’instructions d’un programme: q1 ⋆ * q2 q1 1 * q2 q2 ⋆ s q2 q2 1 s q2 Sous forme d’automate: q1 start q2 ∗,∗ 1,∗ ∗,s 1, s I : Machine de Turing qui imprime ∗et s’arrête. A l’état q1 si la tête de lecture/écriture pointe une case vide alors elle fait rien sinon imprime ∗ et passe à l’état q2 et stoppe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . La machine R : fait avancer à droite jusqu’à la première case vide Sous forme d’instructions d’un programme: q1 ⋆ r q2 q1 1 r q2 q2 ⋆ s q2 q2 1 r q2 Sous forme d’automate: q1 start q2 *,r 1,r *,s 1, r R: Machine de Turing se déplace à droite et s’arrête à la première case vide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . La machine L : fait avancer à gauche jusqu’à la première case vide Sous forme d’instructions d’un programme: q1 ⋆ l q2 q1 1 l q2 q2 ⋆ s q2 q2 1 l q2 Sous forme d’automate: q1 start q2 ∗,l 1,l ∗,s l, r L: Machine de Turing se déplace à droite et s’arrête à la première case vide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R : déplace la tête à droite jusqu’à la première case contenant 1 Sous forme d’instructions d’un programme: q1 ⋆ r q2 q1 1 r q2 q2 ⋆ r q2 q2 1 s q2 Sous forme d’automate: q1 start q2 *,r 1,r *,r 1, s R : Machine de Turing se déplace à droite et s’arrête à la première case non vide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . L : déplace la tête à gauche jusqu’à la première case contenant 1 Sous forme d’instructions d’un programme: q1 ⋆ l q2 q1 1 l q2 q2 ⋆ l q2 q2 1 s q2 Sous forme d’automate: q1 start q2 ∗,l 1,l ∗,l 1, s L : Machine de Turing se déplace à gauche et s’arrête à la première case non vide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Convention Convention: Nous convenons, pour calculer une fonction f(x1, . . . , xn), la tête de lecture/écriture de la machine de Turing doit, initialement, se placer sur la première case vide à gauche des données x1, ..., xn. Le calcul terminé la tête de lecture doit être placée à gauche du résultat. . . . . 6 6 . 6 6 6 6 6 6 Configuration initiale tête de lecture et écriture ⋆ ⋆ 1 1 1 ... ... 1 1 1 1 1 ... Configuration finale 1ere donnée 2eme donnée résultat ⋆ 1 ⋆ 1 1 1 ⋆ ⋆ ⋆ ⋆ 1 ⋆ 1 1 1 ⋆ 1 1 ⋆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Composition de Machine de Turing On peut définir des Machine de Turing plus complexes par concaténation de machines plus simples. M N N * 1 MN : Concaténation de M et N. Après l’exécution de M, on exécute la machine N. Ceci quelque soit l’état final de M. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemples Considérons par exemple la machine de Turing notée K qui recopie une donnée en séparant la donnée et la copie par une marque ’⋆. . . . 1 1 ∗ 1 1 ∗ ∗ . . . Ruban entrée/sortie q0 R l ∗ R2 1 L2 1 l R * 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemples suite La machine calculant la fonction successeur S(x) = x +1 est: K R 1 L. La machine calculant l’addition est la machine : K2 R 1 L et où K2 est la machine qui permet de faire la copie de deux arguments et elle est donnée par: K2 = B2B2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Suite... Définition de B2. R l ∗ R3 1 L3 1 l R * 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemples ....Suite . . . * 1 1 1 1 1 1 . . . Configuration initiale q0 q0 q1 q2 q3 uploads/Industriel/ mturing-slide.pdf