D'abord, un petit exercice de conception d'une MT (assez) simple :
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.
: vraiment besoin de diagrammes!
fait un pas à droite (quelque soit sa lecture
1) ) : R et, éventuellement, R
2, R
k 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}}
Machine a trouver un début de mot (à sa droite) puis de copier le premier caractère du mot en suffixe au mot.
Machine à décaler à droite.
Pour un machine M=\left(K,\Sigma,\delta,s,H\right) et un mot en entrée de la machine \omega \in \left(\Sigma\setminus\left\{\triangleright,\sqcup\right\}\right)^* une configuration initiale est configuration de la forme \left(s,\triangleright\sqcup\omega\right)
Soit M=\left(K,\Sigma,\delta,s,\left\{y,n\right\}\right).
On appelle configuration acceptée ou réussie de M une configuration de la forme \left(y,\omega\right).
On appelle configuration rejettée ou échouée de M une configuration de la forme \left(n,\omega\right).
On dit que M accepte le mot \displaystyle \omega \quad \Leftrightarrow \; \left(s,\triangleright \sqcup \omega\right) \vdash_M^* \;\left(y,\omega\prime\right)
On dit que M rejette le mot \displaystyle \omega \quad \Leftrightarrow \; \left(s,\triangleright \sqcup \omega\right) \vdash_M^* \;\left(n,\omega\prime\right)
On dit que M décide un langage L\subset\Sigma_0^* \subset\Sigma\setminus\left\{\triangleright, \sqcup\right\} si et seulement si \forall \omega\in\Sigma_0^*
Un langage L est dit récursif si et seulement si il existe une machine Turing qui le décide.
Si \Sigma_0=\left\{a,b,c\right\}, L=\left\{a^n b^n c^n |n\in\mathbb{N}\right\} est récursif.
Preuve
un schéma/diagramme à rajouter
\left\{a^n | n \text{premier} \right\}
encore un schema
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.
