===== Composition de Machines de Turing =====

D'abord, un petit exercice de conception d'une MT (assez) simple :

==== Exercice : MT qui inverse a et b ====

Pour un MT avec <jsm>\Sigma = \left\{\triangleright, \sqcup, a,b,c\right\}</jsm>, trouver une MT qui change ''a'' en ''b'' et ''b'' en ''a''.

S = symbole lu
Q = état

^ q<sub>i</sub> ^ s<sub>j</sub> | q<sub>ij</sub> | s<sub>ij</sub> | d<sub>ij</sub>| 
| 0 | > | 0 |  | -> | Si début de ruban, on avance à droite |
| 0 | c | 0 |  | -> | si on lit ''c'' on avance au caractère suivant |
| 0 | a | 1 | b |  | si on lit ''a'' on écrit ''b'' et se prépare à avancer en passant à l'état 1 |
| 0 | b | 1 | a |  | si on lit ''b'' on écrit ''a'' et se prépare à avancer en passant à l'état 1 (ou un autre état encore?) |
| 0 | _ | H | _ |  | si on lit un espace, on a atteint la fin des symboles et on s'arrête |
| 1 | * | 0 |  | -> | on avance à droite après avoir changé un caractère, et on se remet en état de lecture |

Je pense qu'on aurait pu faire plus simplement si on accepte que la tête bougera toujours au lieu de séparer écriture de symbole et écriture de movement et ajouter un état pour le mouvement seul (en quelque sorte).  Un tableau à la Minsky aurait été 

^ q<sub>i</sub> ^ s<sub>j</sub> | q<sub>ij</sub> | s<sub>ij</sub> | d<sub>ij</sub>| 
| 0 | > | 0 |  | -> | Si début de ruban, on n'écrit rien, on bouge à droite |
| 0 | c | 0 |  | -> | si on lit ''c'', on n'écrit rien, on bouge à droite |
| 0 | a | 1 | b | -> | si on lit ''a'' on écrit ''b'' et bouge à droite |
| 0 | b | 1 | a | -> | si on lit ''b'' on écrit ''a'' et bouge à droite |
| 0 | _ | H | _ |  | si on lit un espace, on a atteint la fin des symboles et on s'arrête |

==== Composition de MT ====

  * Machine élémentaire <jsm>M_a = \left(K,\Sigma, s,\delta,\left\{h\right\}\right),\quad K=\left\{s,h\right\},\quad a \in\Sigma, \sigma\ne\triangleright\;\Rightarrow\;\delta\left(s,\sigma\right)=\left(h,a\right) </jsm>
    * <jsm>M_a : a,\quad a\in\Sigma\setminus \left\{\triangleright\right\}</jsm>
    * <jsm>M_\rightarrow : R </jsm>
    * <jsm> M_\leftarrow : L</jsm>
    * <jsm> H =\left(\left\{ s,h\right\}, \Sigma, \delta, s,\left\{h\right\}\right)</jsm>, <jsm>\delta\left(s,\sigma\right) = \left(h,\sigma\right)\quad \sigma\in\Sigma\setminus\left\{\triangleright\right\}</jsm>
      * variantes de H : <jsm> Y =\left(\left\{ s,y\right\}, \Sigma, \delta, s,\left\{y\right\}\right)</jsm>,<jsm> N =\left(\left\{ s,n\right\}, \Sigma, \delta, s,\left\{n\right\}\right)</jsm>

Graphiquement, un exemple <jsmath>
\begin{eqnarray}
M_1 & \rightarrow^a & M_2 \\ 
\downarrow b &  &  \\ 
M_3
\end{eqnarray}
</jsmath>

Plus formellement, cette composition de 3 MT est une machine définie par
<jsmath>
\begin{eqnarray}
M_1 & = & \left(K_1, \Sigma, \delta_1, s_1, H_1\right) \\  
M_2 & = & \left(K_2, \Sigma, \delta_2, s_2, H_2\right) \\  
M_3 & = & \left(K_3, \Sigma, \delta_3, s_3, H_3\right) \\  
M & = & \left(K_1 \cup K_2 \cup K_3 \cup\left\{h\right\}, \Sigma, s_1, H_2\cup H_3\cup \left\{h\right\}\right) \\   
\end{eqnarray}
</jsmath>

<jsmath>
\delta\left(p,\sigma\right) =\left\{
\begin{array}
 \delta_1\left(p,\sigma\right) & \Leftarrow & p\in K_1\setminus H_1 \\  
 \delta_2\left(p,\sigma\right) & \Leftarrow & p\in K_2\setminus H_2 \\  
 \delta_3\left(p,\sigma\right) & \Leftarrow & p\in K_3\setminus H_3 \\  
 \left(s_2,\sigma\right) & \Leftarrow & \left(\sigma=a\right)\wedge \left(p\in H_1\right) \\  
\left(s_3,\sigma\right) & \Leftarrow & \left(\sigma=b\right)\wedge \left(p\in H_1\right) \\  
\left(h,\sigma\right) & \Leftarrow & \left(\sigma\ne a\right)\wedge \left(\sigma\ne b\right)\wedge \left(p\in H_1\right) \\
\end{array}
\right.
</jsmath>

==== Exemples Simples et Notations ====

FIXME : vraiment besoin de diagrammes!

=== Machines à déplacement ===

  * fait un pas à droite (quelque soit sa lecture(( hormis début de bande...et pourquoi pas dans ce cas-là?)) ) : R et, éventuellement, R<sup>2</sup>, R<sup>k</sup>
  * se déplace à droite jusqu'à lire un blanc : \$ R_{\sqcup} \$
  * se déplace à droite jusqu'à lire autre qu'un blanc : \$ R_{\sigma} \$ ou à la recherche dans sous-ensemble de caractères : \$ R_{a,c} \$
  * se déplace à droite et s'arrête à la lecture d'un non-blanc : \$ R_{\bar{\sqcup}} \$
  * Les mêmes déplacement à gauche (//left//) : \$ L\quad L_{\sqcup}\quad L_{\sigma}\quad  L_{\bar{\sqcup}} \$

=== Exercice ===

Machine a trouver un début de mot (à sa droite) puis de copier le premier caractère du mot en suffixe au mot.


=== Machines Utilitaires ===

  * Machine à copier
  * Machine à décaler à gauche

=== Exercice (à rendre) ===

Machine à décaler à droite.

==== 4.3 Calculer ave des Machines de Turing ====

  * Pour un machine <jsm>M=\left(K,\Sigma,\delta,s,H\right)</jsm> et un mot en entrée de la machine <jsm>\omega \in \left(\Sigma\setminus\left\{\triangleright,\sqcup\right\}\right)^*</jsm> une __configuration initiale__ est configuration de la forme <jsm>\left(s,\triangleright\sqcup\omega\right)</jsm>

{{page>c_et_c_def_4}}

=== Exemples ===

  * Si <jsm>\Sigma_0=\left\{a,b,c\right\}</jsm>, <jsm>L=\left\{a^n b^n c^n |n\in\mathbb{N}\right\}</jsm> est récursif.
    * Preuve FIXME un schéma/diagramme à rajouter
  * <jsm>\left\{a^n | n \text{premier} \right\}</jsm>
    * FIXME encore un schema

=== Exercices ===

Ecrire une machine de Turing qui décide le langage reconnu par un automate A : 

^ ^ <jsm>\delta</jsm> ^ a ^ b ^
^ > ^ 0 | 1 | 0 |
^ état final si succès ^ 1 | 0 | 1 |

Généraliser cette "traduction" d'automate à MT.