Pour un MT avec \Sigma = \left\{\triangleright, \sqcup, a,b,c\right\}, trouver une MT qui change a en b et b en a.
S = symbole lu
Q = état
| qi | sj | qij | sij | dij | |
| 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é
| qi | sj | qij | sij | dij | |
| 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 |
Machine élémentaire 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)
M_a : a,\quad a\in\Sigma\setminus \left\{\triangleright\right\}
M_\rightarrow : R
M_\leftarrow : L
H =\left(\left\{ s,h\right\}, \Sigma, \delta, s,\left\{h\right\}\right), \delta\left(s,\sigma\right) = \left(h,\sigma\right)\quad \sigma\in\Sigma\setminus\left\{\triangleright\right\}
variantes de H : Y =\left(\left\{ s,y\right\}, \Sigma, \delta, s,\left\{y\right\}\right), N =\left(\left\{ s,n\right\}, \Sigma, \delta, s,\left\{n\right\}\right)
Graphiquement, un exemple
\begin{eqnarray}
M_1 & \rightarrow^a & M_2 \\
\downarrow b & & \\
M_3
\end{eqnarray}
Plus formellement, cette composition de 3 MT est une machine définie par
\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}
\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.
Ecrire une machine de Turing qui décide le langage reconnu par un automate A :
| | \delta | a | b |
| > | 0 | 1 | 0 |
| état final si succès | 1 | 0 | 1 |
Généraliser cette “traduction” d'automate à MT.
: vraiment besoin de diagrammes!