\documentclass{scrartcl}
\usepackage[margin=1in, left=0.5in, right=0.5in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{mathtools}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD6} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[C]{https://louis.jachiet.com/tps.html}
\fancyfoot[R]{9 novembre 2017}
\newcommand{\A}{\mathcal{A}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ls}{{\mathcal{L}_\Sigma}}
\newcommand{\Lc}{{\mathcal{L}}}
\newcommand{\ml}{\mu_{\mathcal{L}}}
\newcommand{\Mn}{M_n(\Ls)}
\newcommand{\Vn}{{M_{n,1}(\Ls)}}
\newcommand{\tr}[1]{\xrightarrow{#1}}
\newcommand{\td}{\tilde{\delta}}
\newcommand{\norm}[1]{\left\lvert#1\right\rvert}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
%  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%solution/print = true
}
\newtheorem{defi}{Definition}

\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}

\newcommand*\fo[1]{\tikz[baseline=(char.base)]{
                \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,trees}

\author{}
%\date{}
\title{TD6 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section{Exemples de Machines de Turing}

\begin{question}
  Soit $\Sigma$ un alphabet de la bande (telle qu'elle est en entrée)
  avec $\#$ marquant la fin du mot d'entrée.  Donner des Machines de
  Turing pour les langages suivants~:
  \begin{itemize}
  \item $L_1 = \{ y~rev(y) \mid y\in \Sigma^* \}$
  \item $L_2 = \{ y y \mid y\in \Sigma^* \}$
  \item $L^*$ pour $L$ un langage récursivement énumérable reconnu par
    une machine de Turing $M$ qui ne lit pas avant le premier
    caractère et efface le contenu de sa bande avant de terminer.
  \end{itemize}
\end{question}

\begin{solution}

  \begin{enumerate}

    \item
  Pour $L_1$, les états sont : $FINISH$, $READ$, $LEFT$, $RIGHT_s$ et
  $CHECK_s$ pour $s\in\Sigma$. $FINISH$ is the end state, $READ$ the
  initial. The machine reads a letter $s$, go to the right compare
  with the rightmost letter and goes back to the beginning.

  \begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
    \node[state,initial] (q_0) {$READ$};
    \node[state,accepting] (q_f) [right=of q_0] {$FINISH$};
    \node[state] (q_2) [below=of q_0] {$CHECK_s$};
    \node[state] (q_1) [right=of q_2] {$RIGHT_s$};
    \node[state] (q_3) [left=of q_2] {$LEFT$};
    \path[->]
    (q_0) edge node {$\#,>,\#$} (q_f)
    (q_1)  edge node {$\#,<,\#$} (q_2)
    (q_2)  edge node {$s,<,\#$} (q_3) 
    (q_1) edge [loop right] node {$s',>,s'$} () 
    (q_3) edge [loop above] node {$s',<,s'$} ()
    (q_0) [bend right] edge node {$s,>,\#$} (q_1)
    (q_3) edge [bend right] node {$\#,>,\#$} (q_0)  ;

  \end{tikzpicture}


  \item 
  Pour $L_2$, notre solution va insérer des marqueurs $D$ et $M$. Au
  début on met les deux à la fin puis tant que $D$ n'est pas au début
  on décale $M$ de un et $D$ de deux.

  Dans la suite on a $R_i\tr{s,>,s} R_i$ et $L_i\tr{s,<,s}L_i$. On
  considère le cas du mot vide à part $Init\tr{\#,>,\#} OK$ et à deux
  lettres $Init \tr{x,>,x} \tr{x,>,x} \tr{\#,>,\#}OK$.
    
  On initialise en allant à la fin et $wxy\#$ devient $wDxMy\#$ :

  $Init \tr{s,>,s} R_1 \tr{x,>,D} I_2(x) \tr{y,>,x} I_3(y) \tr{\#,>,M} I_4(y) \tr{\#,<,y} L_{pousse} $

  ensuite on pousse $M$ une fois et $D$ deux ($w_1xyDw_2zMw_3$ devient $w_1Dxyw_2Mzw_3$):

  $L_{pousse} \tr{M,<,z} P_1(z) \tr{z,<,M} L_2 \tr{D,<,y} P_2(x,y) \tr{y,<,x} P_3(x) \tr{x,<,D} T_{debut}$

  $T_{debut}$ va tester si on est début si c'est le cas on testera que
  notre mot est de la forme $DyMy\#$ si ce n'est pas le cas il faut
  retourner à gauche et repousser donc $T_{debut}\tr{\#,>,\#} Check $ et
  $T_{debut}\tr{s,>,s}R_{pousse} \tr{M,<,z} P_1(z)$.

  Enfin pour vérifier on va simplement remplacer chaque lettre $s$ vue
  à gauche par un marqueur $D$ et à droite par $M$.

  $Check \tr{s,>,D} R_{check}(s) \tr{M,>,M} R_{check2}(s)\tr{s,<,M} L_{debut} \tr{D,>,D},Check$

  Enfin on a une condition échappatoire $Check \tr{D,>,D} B\tr{M,>,M}B\tr{\#,>,\#}OK$ 

\item Pour $L^*$ on a tester toutes les coupures $w=x_1x_2\dots x_n$
  et transformer $w$ en $x_1\$x_2\dots \$x_n$ puis lancer $M$ sur
  $x_n$, si ça termine en $OK$ alors lancer $M$ sur $x_{n-1}$ etc.

  Pour découper la bande
  $R_{init}\tr{s,>,s}R_{init}\tr{s,>,\$}M_s\tr{u,>,s}M_u\tr{\#,<,u}Ret\tr{s,<,s}Ret\tr{\$,>,\$}R_{init}$

  Pour revenir au dernier $\$ $ quand on atteint la fin: $R_{init}\tr{\#,<,\#}Last\$\tr{s\neq \$,<,s}Last\$ $

  Pour reconnaître via $M$ : $Last\$ \tr{\$,>,\$} M_init$ et continuer si besoin $M_{OK}\tr{\#,<,\#}\tr{\$,<,\#}Last\$$
  ou finir si on a tout reconnu $M_{OK}\tr{\#,<,\#}\tr{D,>,\#}OK$
  \end{enumerate}
\end{solution}

\begin{question}
On suppose que les entiers sont écrits en binaire. Les entrées sorties
sont faites sur la bande qui contient $k$ nombres. Pour $k$ nombres,
la bande est $((0^*1^*)^*\#)^k$ ($k$ fois des $0$ et $1$ suivis de
$\#$). Décrire des machines de Turing pour réaliser les opérations
suivantes (à chaque fois la bande de fin doit contenir un nombre,
c'est à dire des $0$ et des $1$ suivis de $\#$)~:
\begin{enumerate}
  \item passer de petit-boutien à grand-boutien (et vice-versa);
  \item calculer la somme de deux entiers ;
  \item étant donnés deux machines $M_1$ et $M_2$ qui calculent deux
    fonctions $f_1$ et $f_2$, donner un machine qui calcule $f_2\circ
    f_1$.
\end{enumerate}
\end{question}

\begin{solution}
  \begin{enumerate}
  \item
    Cas du mot vide $init\tr{\#,>,\#}OK$

    Cas général on va à la fin, $init\tr{s,>,s}init\tr{\#,<,\$}Push$

    Notre tête est à la fin sur la dernière lettre, on va pousser les
    lettres vers le début,
    $Push\tr{u,<,\$}P_u\tr{s,<,u}P_s\tr{\#,>,\#}A_s$

    $A_s$ va poser $s$ après le premier $\$ $ rencontré (notez qu'on
    en avait laissé deux notre tête est sur la dernière lettre non
    retournée) : $A_s\tr{u,>,u}A_s\tr{\$,<,s}Push$

    Maintenant quand $Push$ lit un $\$ $ c'est qu'on a fini de
    retourner, il suffit de supprimer ce $\$ $ en poussant les lettres
    depuis la fin :
    $Push\tr{\$,>,\#}End\tr{s,>,s}End\tr{\#,<,\#}Push_2\tr{s,<,s}P^2_s\tr{u,<,s}P^2_u\tr{\#,>,u}OK$.

    \item On suppose que les nombres sont en petit-boutien de la forme
      $x_1+x_2$ : on décale pour mettre de la forme $\$x_1+x_2$ et
      à chaque fois on va transformer pour ce soit de la forme
      $w\$w_10^{|w|}+w_2$ avec $|w_i|+|w|=|x_i|$.

      $init\tr{s,>,\$}push_s\tr{u,>,s}push_u \tr{\#,<,u} beg \tr{s,<,s} beg \tr{\$,>,\$} ha_0$

      on est retourné au début on peut faire notre half-adder $ha_i$ pour $i\in\{0,1\}$:

      $ha_i\tr{s,>,s}ha^2_{s+i}\tr{u,>,u}ha^2_{s+i}\tr{+,>,0}ha^3_{s+i}\tr{v,<,+}ha^4_{s+v+i}
      \tr{u,<,u}ha^4_{s+v+i} \tr{\$,>,(s+v+i) mod 2}ha_{(s+v+i)\div 2}$.

      La condition d'échappement de $ha_i$ est $ha_i\tr{\#,>,i}OK$
      
  \end{enumerate}
\end{solution}

\section{Stabilité des langages récursivement énumérables, décidables, etc.}

Soient $A$, $B$ des langages décidables et $C$ et $D$ des langages
récursivement énumérables.

\begin{question}
  Pour chacune des paires $(X,Y)$ parmi $(A,B)$, $(B,C)$, $(C,D)$ et $(D,A)$
  est-ce que $L_{X,Y}$ est nécessairement décidable ou énumérable pour
  les langages suivants~:
\begin{enumerate}
    \item $L_{X,Y}=X\cap Y$
    \item $L_{X,Y}=X\cup Y$
    \item $L_{X,Y}=X\setminus Y$  
\end{enumerate}
\end{question}

\begin{solution}  
$X\cap Y$ est nécessairement décidable quand $X$ et $Y$ le sont et
  énumérables quand $X$ et $Y$ le sont. Pareil pour $X\cup Y$.

  $X\setminus Y$ est décidable si $X$ et $Y$ le sont mais n'est
  nécessairement énumérable que dans le cas $Y$ décidable et $X$
  énumérable.
\end{solution}

\begin{question}
  Montrer que si $X$ et $\bar{X}$ sont énumérables alors $X$ est décidable.
\end{question}

\begin{solution}
Pour décider de $m\in X$, on énumère simultanément $X$ et $\bar{X}$ et
dès que l'on trouve $m\in X$ ou $m\in \bar{X}$ on peut répondre. Comme
les deux tests tournent simultanément, la partie $X$ termine forcément
quand $m\in X$ et la partie $\bar{X}$ termine sinon.
\end{solution}

\section{Machines de Turing exotiques}
\begin{itemize}
\item Une machine à $k$ piles est une machine de Turing avec une bande
  d’entrée et $k$ bandes de travail, où les bandes de travail sont
  remplacées par des piles ;

\item  une
machine à file
est une machine de Turing avec une bande d’entrée et une bande
de travail, où les bandes de travail sont remplacées par des files : on peut ajouter des
éléments part la gauche et les lire par la droite ;

\item une machine à $k$ compteurs est une machine à $k$ piles où
  l’alphabet de pile est $\{B,Z\}$ et $Z$ est un symbole de fond de
  pile. Un entier $i$ peut-être stocké dans une pile en comptant le
  nombre de symboles $B$. On peut incrémenter, décrémenter le compteur
  et tester si le compteur est vide (symbole $Z$ en tête de pile).
\end{itemize}

\begin{enumerate}
\item Montrer qu’une machine de Turing est équivalente à une machine à
  deux piles.
  
\item Montrer qu’une de Turing est équivalente à une machine à une
  file.
  
\item Montrer qu’une machine à une pile peut-être simulée par une
  machine à deux compteurs.

\item Montrer qu’une machine de Turing est équivalente à une machine à
  deux compteurs.

\end{enumerate}

\begin{solution}
\begin{enumerate}
\item L'idée c'est de stocker l'état de la bande sur deux piles
  $(G,D)$. Quand on faire bouger la tête de la MT vers la droite on
  lit dans $D$ et on écrit dans $G$ et inversement pour aller à gauche
  on lit dans $G$ et écrit dans $D$.

\item L'idée c'est qu'on stocke l'état $m_1 \dots m_k m_{k+1} \dots
  m_n$ sous la forme de la file $m_k \dots m_1 \# m_n \dots m_{k+1}$
  quand on est sur l'élément $m_k$ et qu'on veut lire la bande vers la
  droite. Quand on veut lire vers la gauche on ajoute un deuxième
  symbole $T$ pour dire qu'il faut faire le tour de la file et on lit
  les éléments jusqu'à trouver ce $T$, le dernier élément alors lu
  correspond à l'élément strictement à gauche.

\item L'idée c'est qu'une pile $p_0 \dots p_n$ dont l'alphabet est
  $\{B, Z\}$ peut être vu comme un nombre $\Sigma_{p_k=B} 2^k$. Notre
  compteur $C_1$ va donc stocker l'état de la pile de cette
  façon. Pour lire le dernier élément de la pile il faut diviser $C_1$
  par deux. Pour cela on répète tant que nécessaire prendre deux
  éléments dans $C_1$ pour en mettre un dans $C_2$. À la fin il nous
  reste un ou zéro élément dans $C_1$, ça nous dit si l'état du haut
  de la pile est $B$ ou $Z$.

  On vide alors l'éventuel élément restant dans $C_1$ puis on
  déplace le contenu de $C_2$ dans $C_1$ en répétant tant que possible
  prendre un dans $C_2$ et le mettre dans $C_1$.

  Pour empiler un élément on multiplie $C_1$ par deux (copier $C_1$
  dans $C_2$ puis répéter ``prendre un dans $C_2$ et mettre deux dans
  $C_1$'') puis on ajoute un si l'élément à ajouter est $B$.

\item On va produire une machine à 4 compteurs avec une machine à deux
  compteurs.  Pour cela $C_1$ va contenir ${p_1}^{d_1} {p_2}^{d_2}
  {p_3}^{d_3} {p_4}^{d_4}$ avec $p_1=2, p_2=3, p_3=5, p_4 =7$.  Pour
  incrémenter un compteur $i$ on multiplie par $p_i$, pour décrémenter
  on divise par $p_i$ et pour tester si un compteur est vide on tester
  le résultat de $C_1 mod p_i$.

  Avec ces 4 compteurs on en dédit deux pour faire une pile et deux
  autres pour faire une deuxième pile. Une machine avec deux piles
  pouvant simuler une MT, le résultat est obtenu.

  
\end{enumerate}

\end{solution}

\end{document}

