TD sur les machines de Turing

Igor Stéphan 16 mars 1999

Références

1 Les langages a^{n}b^{n} et a^{n}b^{n}c^{n}

Machine de Turing pour décider du langage a^{n}b^{n} . Montrer que la machine de Turing M_{1} ci-dessous dérive (en plusieurs étapes) la configuration (q_{4}, XXY Y #, ε) de (q_{0}, ε, aabb).

M_{1} = ({q_{0}, q_{1}, q_{2}, q_{3}, q_{4}}, {a, b, X, Y, #}, {a, b}, δ, q_{0}, #, {q_{4}})

avec

δ = {((q_{0}, a), (q_{1}, X, d)) 1) Un a a été trouvé alors il est remplacé par un X et un b est recherché. ((q_{1}, a), (q_{1}, a, d))  2) Les a sont traversés à la recherche d’un b. ((q_{1}, Y), (q_{1}, Y, d)) 3) Les Y sont traversés à la recherche d’un b. ((q_{1}, b), (q_{2}, Y, g))  4) Un b a été trouvé alors il est remplacé par un Y et un a est recherché en arrière. ((q_{2}, Y), (q_{2}, Y, g)) 5) Les Y sont traversés à la recherche d’un X. ((q_{2}, a), (q_{2}, a, g))  6) Les a sont traversés à la recherche d’un X. ((q_{2}, X), (q_{0}, X, d)) 7) Un X a été trouvé alors à nouveau un a doit etre sur la droite ((q_{0}, Y), (q_{3}, Y, d)) 8) Il n’y a plus de a alors il ne doit plus y avoir ni de b ni de c. ((q_{3}, Y), (q_{3}, Y, d)) 9) Les Y sont traversés à la recherche d’un #. ((q_{3}, #), (q_{4}, #, d)) 10) Le mot d’entré a été décidé comme appartenant au langage a^{n}b^{n}. ((q_{0}, #), (q_{4}, #, d))} 11) ε ∈ a^{n}b^{n}

(q_{0}, ε, aabb) 3 (q_{1}, XXY, b)
1 (q_{1}, X, abb) 4 (q_{2}, XX, Y Y)
2 (q_{1}, Xa, bb) 5 (q_{2}, X, XY Y)
4 (q_{2}, X, aY b) 7 (q_{0}, XX, Y Y)
6 (q_{2}, ε, XaY b) 8 (q_{3}, XXY, Y)
7 (q_{0}, X, aY b) 9 (q_{3}, XXY Y, ε)
1 (q_{1}, XX, Y b) 10 (q_{4}, XXY Y #, ε)

Machine de Turing pour décider du langage a^{n}b^{n}c^{n} .

M = ({q_{a}, q_{b}, q_{c}, q_{X}, q_{v}, q_{f}}, {a, b, c, X, Y, Z, #}, {a, b, c}, δ, q_{a}, #, {q_{f}})

avec

δ = {((q_{a}, a), (q_{b}, X, d)) 1) Un a a été trouvé alors il est remplacé par un X et un b est recherché. ((q_{b}, a), (q_{b}, a, d))  2) Les a sont traversés à la recherche d’un b. ((q_{b}, Y), (q_{b}, Y, d)) 3) Les Y sont traversés à la recherche d’un b. ((q_{b}, b), (q_{c}, Y, d))  4) Un b a été trouvé alors il est remplacé par un Y et un c est recherché. ((q_{c}, b), (q_{c}, b, d))  5) Les b sont traversés à la recherche d’un c. ((q_{c}, Z), (q_{c}, Z, d)) 6) Les Z sont traversés à la recherche d’un c. ((q_{c}, c), (q_{X}, Z, g)) 7) Un c a été trouvé alors il est remplacé par un Z et un a est recherché en arrière ((q_{X}, Z), (q_{X}, Z, g)) 8) Les Z sont traversés à la recherche d’un X. ((q_{X}, b), (q_{X}, b, g)) 9) Les b sont traversés à la recherche d’un X. ((q_{X}, Y), (q_{X}, Y, g)) 10) Les Y sont traversés à la recherche d’un X. ((q_{X}, a), (q_{X}, a, g)) 11) Les a sont traversés à la recherche d’un X. ((q_{X}, X), (q_{a}, X, d)) 12) Un X a été trouvé alors à nouveau un a doit etre sur la droite ((q_{a}, Y), (q_{v}, Y, d)) 13) Il n’y a plus de a alors il ne doit plus y avoir ni de b ni de c. ((q_{v}, Y), (q_{v}, Y, d)) 14) Les Y sont traversés à la recherche d’un #. ((q_{v}, Z), (q_{v}, Z, d)) 15) Les Z sont traversés à la recherche d’un #. ((q_{v}, #), (q_{f}, #, d)) 16) Le mot d’entré a été décidé comme appartenant au langage a^{n}b^{n}c^{n}. ((q_{a}, #), (q_{f}, #, d))} 17) ε ∈ a^{n}b^{n}c^{n}

2 Machine de Turing et fonctions

Machine de Turing pour décider de l’addition des entiers naturels . Écrire une machine de Turing pour additionner deux nombres entiers dans une représentation binaire.

M_{add} = ({s, q_{1}, q′_{1}, q_{0}, q′_{0}, r, n, b, f}, {0, 1, U, Z, $, #}, {1, 0}, δ, s, #, {f})

avec

δ = {((s, 1), (q_{1}, #, d)) 1) Le bit du premier opérande est 1 alors le bit correspondant du second opérande est recherché. ((s, 0), (q_{0}, #, d)) 2) Le bit du premier opérande est 0 alors le bit correspondant du second opérande est recherché. ((q_{1}, 1), (q_{1}, 1, d)) 3) Les 1 sont traversés en recherche de l’opérande. ((q_{1}, 0), (q_{1}, 0, d)) 4) Les 0 sont traversés en recherche de l’opérande. ((q_{0}, 1), (q_{0}, 1, d)) 6) Les 1 sont traversés en recherche de l’opérande. ((q_{0}, 0), (q_{0}, 0, d)) 7) Les 0 sont traversés en recherche de l’opérande. ((q_{1}, $), (q′_{1}, $, d)) 8) Le $ signale l’entrée dans le second opérande. ((q_{0}, $), (q′_{0}, $, d)) 9) Le $ signale l’entrée dans le second opérande. ((q′_{1}, U), (q′_{1}, U, d)) 10) Les U sont traversés dans le second opérande. ((q′_{1}, Z), (q′_{1}, Z, d)) 11) Les Z sont traversés dans le second opérande. ((q′_{0}, U), (q′_{0}, U, d)) 12) Les U sont traversés dans le second opérande. ((q′_{0}, Z), (q′_{0}, Z, d)) 13) Les Z sont traversés dans le second opérande. ((q′_{1}, 0), (b, U, g)) 14) 1 ∗ 2^{n} + 0 ∗ 2^{n} = 1 ∗ 2^{n} donc positionnement du bit à 1. ((q′_{1}, 1), (r, Z, d)) 15) 1 ∗ 2^{n} + 1 ∗ 2^{n} = 1 ∗ 2^{n+1} donc positionnement du bit à 0 et propagation de la retenue au second opérande. ((q′_{0}, 0), (b, Z, g)) 16) 0 ∗ 2^{n} + 0 ∗ 2^{n} = 1 ∗ 2^{n} donc positionnement du bit à 0. ((q′_{0}, 1), (b, U, g)) 17) 0 ∗ 2^{n} + 1 ∗ 2^{n} = 1 ∗ 2^{n} donc positionnement du bit à 1. ((q′_{1}, #), (b, U, g)) 18) Les bits en plus du premier opérande sont ajoutés. ((q′_{0}, #), (b, Z, g)) 19) Les bits en plus du premier opérande sont ajoutés. ((r, 1), (r, 0, d))  20) 1 ∗ 2^{n} + 1 ∗ 2^{n} = 1 ∗ 2^{n+1} donc positionnement du bit à 0 et poursuite de la propagation de la retenue. ((r, 0), (b, 1, g))  21) 1 ∗ 2^{n} + 0 ∗ 2^{n} = 1 ∗ 2^{n} donc positionnement du bit à 1 et arret de la propagation de la retenue. ((r, #), (b, 1, g))  22) 1 ∗ 2^{n} + 0 ∗ 2^{n} = 1 ∗ 2^{n} donc positionnement du bit à 1 et arret de la propagation de la retenue. ((b, U), (b, U, g)) 23) Les U sont traversés à la recherche d’un # ((b, Z), (b, Z, g)) 24) Les Z sont traversés à la recherche d’un # ((b, 1), (b, 1, g))  25) Les 1 sont traversés à la recherche d’un # ((b, 0), (b, 0, g))  26) Les 0 sont traversés à la recherche d’un # ((b, $), (b, $, g))  27) Le $ est traversé à la recherche d’un #

((b, #), (s, #, d)) 28) Une nouvelle addition d’un bit.
((s, $), (n, $, d)) 29) Le remplacement des U et des Z.
((n, U), (n, 1, d)) 30) Le remplacement des U par 1.
((n, Z), (n, 0, d)) 31) Le remplacement des Z par 0.
((n, 0), (n, 0, d)) 32) La traversée des 0 à la recherche d’un #.
((n, 1), (n, 1, d)) 33) La traversée des 1 à la recherche d’un #.
((n, #), (f, #, g)) 34) L’addition est terminée

Les nombres sont représentés avec leurs bits de poids faibles à gauche. La propagation de la retenue suit la formule :

\begin{aligned}& 1 ∗ 2^{n} + (1 ∗ 2^{n} + … + 1 ∗ 2^{n+p} + 0 ∗ 2^{n+p+1} + (0 | 1) ∗ 2^{n+p+2} + …) \\ = & 0 ∗ 2^{n} + … + 0 ∗ 2^{n+p} + 1 ∗ 2^{n+p+1} + (0 | 1) ∗ 2^{n+p+2} + … \end{aligned}

Exemple : 149 + 3

\begin{aligned}& (s, ε, 10101001$11) \\ 1 & (q_{1}, #, 0101001$11) \\ 4 & (q_{1}, #0, 101001$11) \\ 3 & (q_{1}, #01, 01001$11) \\ 4 & (q_{1}, #010, 1001$11) \\ 3 & (q_{1}, #0101, 001$11) \\ 4 & (q_{1}, #01010, 01$11) \\ 4 & (q_{1}, #010100, 1$11) \\ 3 & (q_{1}, #0101001, $11) \\ 8 & (q′_{1}, #0101001$, 11) \\ 15 & (r, #0101001$Z, 1) \\ 20 & (r, #0101001$Z0, #) \\ 22 & (b, #0101001$Z, 01) \\ & … \\ 26 & (b, ε, #0101001$Z01) \\ 28 & (s, #, 0101001$Z01) \\ 2 & (q_{0}, ##, 101001$Z01) \\ & … \\ 6 & (q_{0}, ##101001, $Z01) \\ 9 & (q′_{0}, ##101001$, Z01) \\ 13 & (q′_{0}, ##101001$Z, 01) \\ 16 & (b, ##101001$, ZZ1) \end{aligned} \begin{aligned}& … \\ 25 & (b, #, #101001$ZZ1) \\ 28 & (s, ##, 101001$ZZ1) \\ 1 & (q_{1}, #^{2}#, 01001$ZZ1) \\ & … \\ 3 & (q_{1}, #^{2}#01001, $ZZ1) \\ 8 & (q′_{1}, #^{2}#01001$, ZZ1) \\ 11 & (q′_{1}, #^{2}#01001$Z, Z1) \\ 11 & (q′_{1}, #^{2}#01001$ZZ, 1) \\ 15 & (r, #^{2}#01001$ZZZ, #) \\ 22 & (b, #^{2}#01001$ZZ, Z1) \\ & … \\ 26 & (b, ##, #01001$ZZZ1) \\ 28 & (s, #^{2}#, 01001$ZZZ1) \\ 2 & (q_{0}, #^{3}#, 1001$ZZZ1) \\ 6 & (q_{0}, #^{3}#1001, $ZZZ1) \\ 9 & (q′_{0}, #^{3}#1001$, ZZZ1) \\ & … \end{aligned} \begin{aligned}13 & (q′_{0}, #^{3}#1001$ZZZ, 1) \\ 17 & (b, #^{3}#1001$ZZ, ZU) \\ & … \\ 25 & (b, #^{2}#, #1001$ZZZU) \\ 28 & (s, #^{3}#, 1001$ZZZU) \\ 1 & (q_{1}, #^{4}#, 001$ZZZU) \\ & … \\ 3 & (q_{1}, #^{4}#001, $ZZZU) \\ 8 & (q′_{1}, #^{4}#001$, ZZZU) \\ & … \\ 10 & (q′_{1}, #^{4}#001$ZZZU, #) \\ 18 & (b, #^{4}#001$ZZZ, UU) \\ & … \\ 26 & (b, #^{3}#, #001$ZZZUU) \\ 28 & (s, #^{3}#, #001$ZZZUU) \end{aligned}