\[\newcommand\Nat{\mathbb{N}} \newcommand\set[1]{\left\{#1\right\}} \newcommand\setcompr[2]{\left\{#1\;\middle|\;#2\right\}} \newcommand\Turing{ {\Bbb{T}}\paren{\Sigma}} \newcommand\size[1]{\left|#1\right|} \newcommand\eqdef{\mathrel{:=}} \newcommand\Lang[1]{\mathcal{L}\left(#1\right)} \newcommand\tuple[1]{\left\langle #1\right\rangle} \newcommand\paren[1]{\left( #1\right)} \newcommand\MT{\mathcal{M}}\]
Exercice 1 : Machines de Turing qui reconnaîssent des langages
Proposer des machine de Turing reconnaissant chacun des langages suivants.
a - les mots qui contiennent le motif \(\tt{abba}\)
\[L_1\eqdef\setcompr{w\in\set{ {\tt a},{\tt b}}^\star}{\exists u,v\in\set{ {\tt a},{\tt b}}^\star:\;w=u\,{\tt abba}\,v}\]
Solution :
Solution :
b - les mots qui ont deux fois plus de \(\tt{a}\) que de \(\tt{b}\).
\[L_2\eqdef\setcompr{w\in\set{ {\tt a},{\tt b}}^\star}{\size{w}_{\tt a}=2\times\size{w}_{\tt b}}\]
Solution :
Solution :
c - les séquences de \(\tt{a}\) dont la longueur est une puissance de 2.
\[L_3\eqdef\setcompr{ {\tt a}^{2^n}}{n\in\Nat}\]
Solution :
Exercice 2 : Les carrés
Les machines de Turing peuvent reconnaître plus que les langages hors-contexte.
C’est le cas par exemple du langage \(L\eqdef\setcompr{ww}{w\in\set{ {\tt a},{\tt b}}^\star}\) des carrés.
On peut montrer, par exemple avec le lemme de la double étoile, que ce langage n’est pas hors-contexte : il ne peut être défini à l’aide d’une grammaire hors-contexte.
question 1
Écrire une machine de Turing reconnaissant le langage \(w{\tt X}w\), où \(w\in\set{\tt a,\tt b}^\star\).
Solution :
Solution :
question 2
Écrire une machine de Turing qui rejette les mots de longueur impaire, et pour les mots de longueur paire insère le symbole \(\tt X\) entre les deux moitiés du mot. Par exemple, le mot \({\tt abaa}\) est transformé en \({\tt abXaa}\).
Solution :
question 3
Combiner les machines des deux questions précédentes pour en produire une reconnaissant \(L\).
Solution :
question 4 (Bonus)
Montrer que le langage \(L\) n’est pas rationnel.
On utilise le lemme de l’étoile.
Soit un entier \(n\). Le mot \(w={\tt a}^n{\tt b}{\tt a}^n{\tt b}\) est un carré, et appartient donc au langage \(L\).
En revanche pour tout découpage \(w=u_1\,u_2\,u_3\) tel que \(\size{u_1u_2}<n\) et \(u_2\neq\varepsilon\), on observe que le \(u_1u_2\) ne contient que des \({\tt a}\).
Par conséquent, le mot \(u_1\paren{u_2}^0u_3=u_1\,u_3\) est de la forme \({\tt a}^k{\tt b}{\tt a}^n{\tt b}\), avec \(k<n\). Ce mot n’est donc pas un carré, et en temps que tel n’appartient pas à \(L\).
Si \(L\) était régulier, d’après le lemme de l’étoile il existerait un certain entier \(N\) tel que pour tout mot \(w\in L\) de longueur supérieure à \(N\), il existe un découpage \(w=u_1\,u_2\,u_3\) avec \(\size{u_1u_2}<n\) et \(u_2\neq\varepsilon\), tel que pour tout entier \(k\in\Nat\) on aie \(u_1\paren{u_2}^ku_3\in L\). On a montré plus haut une famille de mots arbitrairement longs pour lesquels un tel découpage est impossible, ce qui prouve que \(L\) n’est pas régulier.
Exercice 3 : Machines de Turing qui calculent
\(\newcommand\pcode[1]{\tuple{#1}_{code}}\)
On va manipuler des listes d’entiers, encodées par la fonction \(\pcode{-}\) comme suit:
- les entiers sont encodés en binaire avec le bit de poids fort en tête;
- les éléments d’une liste sont séparés par le symbole \({\tt \$}\);
- la liste est délimitée à gauche et à droite par un symbole \({\tt \$}\).
Par exemple:
| liste |
code |
| [] |
$$ |
| [3] |
$11$ |
| [3,2] |
$11$10$ |
| [1,2,3,4,5,6] |
$1$10$11$100$101$110$ |
question 1
Proposer une machine de Turing qui calcule la fonction \({\tt rev}\), qui inverse l’ordre des éléments d’une liste (d’entiers).
Par exemple, comme \({\tt rev}\left([1,2,3]\right)=[3,2,1]\), on veut une machine qui, si elle est exécutée sur \(\pcode{[1,2,3]}\), produit \(\pcode{[3,2,1]}\).
Solution :
question 2
Proposer une machine de Turing qui calcule la somme des entiers contenus dans une liste. Par exemple, sur l’entrée \(\pcode{[1,2,3]}\), la machine devra produire le mot \({\tt 110}\), qui encode l’entier \(1+2+3=6\).
Solution :
question 3
Proposer une machine de Turing qui calcule la longueur d’une liste (d’entiers). Par exemple, sur l’entrée \(\pcode{[1,2,3]}\), elle produira \({\tt 11}\), c’est à dire la représentation de \(3=\size{[1,2,3]}\).
Solution :
Exercice 4 : Difficulté des problèmes
Pour chacun des problèmes suivants, indiquer s’ils sont:
- rationnels
- non-rationnels mais décidables
- indécidables mais reconnaissables
- ni décidables, ni reconnaissables.
Il est nécessaire dans cet exercice de justifier soigneusement vos réponses.
On appréciera tout particulièrement les justifications claires et concises (également: justes).
Dans la suite, on fixe \(\Sigma=\set{ {\tt a},{\tt b} }\), et on note \(\Turing\) l’ensemble des machines de Turing sur l’alphabet \(\Sigma\).
a - Machines reconnaissant \({\tt ab}\) :
- Instances : \(\MT\in\Turing\)
- Instances Positives : \(\MT\) telle que \({\tt ab}\in\Lang{\MT}\).
Indécidable mais reconnaissable:
- Reconnaissable: on peut simuler l’exécution de \(\MT\) sur \({\tt ab}\). Si la machine accepte, nous aussi.
- Indécidable: réduction à partir du problème de l’arrêt sur le mot vide. On veut savoir si \(\MT\) s’arrète sur le mot vide. On construit une machine \(\MT'\) qui efface son entrée, avant de simuler \(\MT\) sur le mot vide. Si la simulation se termine, alors \(\MT'\) accepte. Si \(\MT\) s’arrête sur le mot vide, alors \(\MT'\) accepte le langage universel, et en particulier elle accepte le mot \({\tt ab}\). Sinon, elle n’accepte aucun mot, et donc \(\MT'\) est une instance négative du problème.
Cette construction nous montre que si on savait résoudre le problème “\(\MT\) accepte-t’elle le mot \({\tt ab}\) ?”, alors on saurait résoudre le problème “\(\MT\) s’arrête-t’elle sur le mot vide ?”. Ce dernier étant indécidable, l’autre l’est également.
- Théorème de Rice: On aurait aussi pu montrer l’indécidabilité avec le théorème de Rice. En effet,
- certaines machines acceptent \({\tt ab}\), et d’autres non : c’est donc une propriété non triviale;
- si \(\Lang{\MT_1}=\Lang{\MT_2}\), alors il est évident que \({\tt ab}\in\Lang{\MT_1}\Leftrightarrow{\tt ab}\in\Lang{\MT_2}\) : c’est donc une propriété de langage.
b - Machines reconnaissant au moins un mot de taille bornée :
- Instances : paires \(\tuple{\MT,n}\), avec \(\MT\in\Turing\) et \(n\in\Nat\)
- Instances Positives : \(\tuple{\MT,n}\) tels que il existe \(w\in\Sigma^\star\) tel que \(\size{w}<n\) et \(w\in\Lang{\MT}\).
Indécidable mais reconnaissable.
- Indécidable: on fait une réduction à partir du problème de l’arrêt sur le mot vide. C’est assez immédiat : \(\MT\) s’arrête sur le mot vide si et seulement si elle accepte un mot de longueur strictement inférieure à 1.
- Reconnaissable : on utilise le non-déterminisme. On énumére les mots de taille inférieure à \(n\), et on en choisit un de manière non déterministe.
Ensuite, on simule la machine fournie en entrée sur ce mot.
Si la paire \(\tuple{\MT,n}\) est une instance positive, alors il existe un choix non-déterministe qui produit une exécution acceptante. Sinon, aucune exécution ne sera acceptante, et l’entrée sera donc rejettée.
c - Paires de machines ayant au moins un mot en commun :
- Instances : paires \(\tuple{\MT_1,\MT_2}\in\Turing\times\Turing\),
- Instances positives : paires \(\tuple{\MT_1,\MT_2}\) telles que \(\Lang{\MT_1}\cap\Lang{\MT_2}\neq\emptyset\).
Indécidable, mais reconnaissable.
- Indécidable : réduction à partir du problème de l’arrêt sur le mot vide. On veut savoir si \(\MT\) s’arrête sur le mot vide. On construit une machine \(\MT'\) qui efface son entrée, avant de simuler \(\MT\) sur le mot vide. Si la simulation se termine, alors \(\MT'\) accepte. On produit ensuite la paire \(\tuple{\MT',\MT_{oui}}\), où la machine \(\MT_{oui}\) ne lit pas son entrée et accepte immédiatement. Le langage de cette machine est donc \(\Sigma^\star\).
- Si \(\MT\) s’arrête sur le mot vide, alors \(\MT'\) accepte le langage universel et donc \(\Lang{\MT'}\cap\Lang{\MT_{oui}}=\Sigma^\star\neq\emptyset\).
- Sinon, elle n’accepte aucun mot, et donc \(\Lang{\MT'}\cap\Lang{\MT_{oui}}=\emptyset\cap\Sigma^\star=\emptyset\).
- Reconnaissable : on utilise le non-déterminisme. On énumère tous les mots sur l’alphabet \(\Sigma\). On en choisit un de manière non-déterministe. On simule les deux machines sur ce mot. Si les deux acceptent, on accepte l’entrée.
- Si la paire forme une instance positive, il existe un mot accepté par les deux machines, et donc une exécution acceptante de notre machine non-déterministe.
- Sinon, sur chaque mot, au moins une des machines n’accepte pas. Il n’y a donc pas d’exécution acceptante de notre machine.
d - Machines avec plus d’états finaux que d’états non-finaux :
- Instances : \(\MT\in\Turing\),
- Instances positives : \(\MT=\tuple{Q,\Sigma,\Delta,q_0,F}\) telle que \(\size{F} \geqslant \size{Q\setminus F}\).
Décidable, mais (probablement) pas rationnel.
La rationnalité de ce problème n’est pas claire, mais il paraît douteux qu’un automate reconnaissant ce langage existe…
En revanche la décidabilité est claire. En effet, pour tester si un code représente une machine ayant plus d’états finaux que non-finaux, il suffit de:
- lire la liste des transitions, en notant tous les états utilisés sur un second ruban
- calculer la longueur de cette liste
- lire la liste des états finaux, en supprimant les doublons éventuels
- calculer la longueur de cette liste
- comparer les deux longueurs qu’on a calculé.
e - Machines sans états finaux :
- Instances : \(\MT\in\Turing\),
- Instances positives : \(\MT=\tuple{Q,\Sigma,\Delta,q_0,F}\) telle que \(F=\emptyset\).
Ce problème est rationnel : il suffit de vérifier que la liste des états finaux est vide. Rappelons nous que le code d’une machine est de la forme \(\$\,liste~des~transitions\,\$\,liste~des~états~finaux\). Une machine est donc une instance positive de ce problème si et seulement si son code appartient au langage suivant:
\[\$\paren{0+1+\#+D+G+\S}^\star\$.\]