%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{Exercices divers — Corrigé}
\else
\title{Exercices divers}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000



%
%
%

\bigbreak
\centerline{\textbf{Langages rationnels et automates}}

\exercice

Soit $\Sigma = \{a,b\}$.

(1) Tracer l'automate de Thompson de l'expression rationnelle
$a{*}(baa{*}){*}$.  Cet automate est-il déterministe ?

(2) En éliminer les transitions spontanées.

(3) Déterminiser l'automate obtenu.

(4) Minimiser l'automate obtenu.

(5) Vérifier le résultat en décrivant en français le langage dénoté
par l'expression rationnelle initiale et reconnu par l'automate
finalement obtenu.

\begin{corrige}
(1) L'automate de Thompson de $a{*}(baa{*}){*}$ doit comporter $14$
  états puisque cette expression rationnelle contient $7$ symboles
  parenthèses non comptées.  Il est le suivant (où on a omis les
  $\varepsilon$ sur les transitions spontanées) :
\begin{center}
\scalebox{0.34}{%
%%% begin ex3p1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,45bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q3) at (255bp,18bp) [draw,circle,state] {$3$};
  \node (q2) at (176bp,45bp) [draw,circle,state] {$2$};
  \node (q5) at (413bp,48bp) [draw,circle,state] {$5$};
  \node (q4) at (334bp,18bp) [draw,circle,state] {$4$};
  \node (q7) at (571bp,86bp) [draw,circle,state] {$7$};
  \node (q6) at (492bp,86bp) [draw,circle,state] {$6$};
  \node (q9) at (729bp,86bp) [draw,circle,state] {$9$};
  \node (q8) at (650bp,86bp) [draw,circle,state] {$8$};
  \node (q11) at (891.49bp,125bp) [draw,circle,state] {$11$};
  \node (q10) at (809.5bp,125bp) [draw,circle,state] {$10$};
  \node (q13) at (1055.5bp,25bp) [draw,circle,state,final] {$13$};
  \node (q12) at (973.49bp,63bp) [draw,circle,state] {$12$};
  \draw [->] (q0) ..controls (59.7bp,17.371bp) and (103.03bp,16.838bp)  .. (140bp,17bp) .. controls (169.56bp,17.13bp) and (203.43bp,17.448bp)  .. node[auto] {{}} (q3);
  \draw [->] (q12) ..controls (939.5bp,48.432bp) and (914.89bp,40bp)  .. (892.49bp,40bp) .. controls (491bp,40bp) and (491bp,40bp)  .. (491bp,40bp) .. controls (474.34bp,40bp) and (455.77bp,41.875bp)  .. node[auto] {{}} (q5);
  \draw [->] (q2) ..controls (203.44bp,35.73bp) and (216.64bp,31.102bp)  .. node[auto] {{}} (q3);
  \draw [->] (q10) ..controls (835.62bp,135.26bp) and (845.21bp,137.3bp)  .. (854bp,136bp) .. controls (856.94bp,135.57bp) and (859.98bp,134.94bp)  .. node[auto] {$a$} (q11);
  \draw [->] (q7) ..controls (598.66bp,86bp) and (610.82bp,86bp)  .. node[auto] {$a$} (q8);
  \draw [->] (q9) ..controls (788.12bp,80.488bp) and (892.85bp,70.553bp)  .. node[auto] {{}} (q12);
  \draw [->] (q8) ..controls (677.66bp,86bp) and (689.82bp,86bp)  .. node[auto] {{}} (q9);
  \draw [->] (q11) ..controls (915.87bp,107.43bp) and (926.56bp,99.325bp)  .. (935.99bp,92bp) .. controls (940.47bp,88.526bp) and (945.22bp,84.783bp)  .. node[auto] {{}} (q12);
  \draw [->] (q2) ..controls (152.62bp,39.018bp) and (146.07bp,37.685bp)  .. (140bp,37bp) .. controls (134.92bp,36.427bp) and (129.53bp,36.741bp)  .. node[auto] {{}} (q1);
  \draw [->] (q6) ..controls (519.66bp,86bp) and (531.82bp,86bp)  .. node[auto] {{}} (q7);
  \draw [->] (q12) ..controls (1002.2bp,49.853bp) and (1016.2bp,43.176bp)  .. node[auto] {{}} (q13);
  \draw [->] (q9) ..controls (756.02bp,98.925bp) and (770.16bp,105.95bp)  .. node[auto] {{}} (q10);
  \draw [->] (q3) ..controls (282.66bp,18bp) and (294.82bp,18bp)  .. node[auto] {{}} (q4);
  \draw [->] (q11) ..controls (866.59bp,118.91bp) and (860.06bp,117.66bp)  .. (854bp,117bp) .. controls (848.92bp,116.45bp) and (843.55bp,116.73bp)  .. node[auto] {{}} (q10);
  \draw [->] (q5) ..controls (440.12bp,60.892bp) and (454.27bp,67.873bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q4) ..controls (366.77bp,7.9414bp) and (390.7bp,2bp)  .. (412bp,2bp) .. controls (412bp,2bp) and (412bp,2bp)  .. (974.49bp,2bp) .. controls (992.87bp,2bp) and (1012.7bp,7.6737bp)  .. node[auto] {{}} (q13);
  \draw [->] (q0) ..controls (45.436bp,27.27bp) and (58.635bp,31.898bp)  .. node[auto] {{}} (q1);
  \draw [->] (q1) ..controls (121.23bp,55.953bp) and (131.02bp,58.496bp)  .. (140bp,57bp) .. controls (143.13bp,56.478bp) and (146.36bp,55.711bp)  .. node[auto] {$a$} (q2);
  \draw [->] (q4) ..controls (361.28bp,28.238bp) and (374.94bp,33.562bp)  .. node[auto] {{}} (q5);
%
\end{tikzpicture}

%%% end ex3p1 %%%
}
\end{center}

Cet automate n'est pas déterministe : un automate comportant des
ε-transitions est forcément non-déterministe.

(2) Tous les états autres que $0$ (car il est initial) et $2,6,8,11$
(car des transitions non spontanées y aboutissent) vont disparaître ;
les ε-fermetures $C(q)$ de ces états sont les suivantes :

\begin{center}
\begin{tabular}{r|l}
$q$&ε-fermeture $C(q)$\\
\hline
$0$&$\{0,1,3,4,5,13\}$\\
$2$&$\{2,3,4,5,13\}$\\
$6$&$\{6,7\}$\\
$8$&$\{5,8,9,10,12,13\}$\\
$11$&$\{5,10,11,12,13\}$\\
\end{tabular}
\end{center}

En remplaçant chaque transition $q^\sharp \to q'$ étiquetée par $x$
dans l'automate par une transition $q\to q'$ pour chaque état $q$ tel
que $q^\sharp \in C(q)$, on obtient le NFA suivant :

\begin{center}
%%% begin ex3p1b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q0) at (18bp,31.498bp) [draw,circle,state,initial,final,accepting below] {$0$};
  \node (q2) at (97bp,61.498bp) [draw,circle,state,final] {$2$};
  \node (q11) at (335.5bp,19.498bp) [draw,circle,state,final,accepting below] {$11$};
  \node (q8) at (255bp,49.498bp) [draw,circle,state,final,accepting above] {$8$};
  \node (q6) at (176bp,31.498bp) [draw,circle,state] {$6$};
  \draw [->] (q0) ..controls (45.279bp,41.737bp) and (58.943bp,47.06bp)  .. node[auto] {$a$} (q2);
  \draw [->] (q2) to[loop above] node[auto] {$a$} (q2);
  \draw [->] (q8) ..controls (282.44bp,39.394bp) and (295.8bp,34.29bp)  .. node[auto] {$a$} (q11);
  \draw [->] (q11) to[loop above] node[auto] {$a$} (q11);
  \draw [->] (q11) ..controls (297.15bp,8.7001bp) and (264.63bp,2.1768bp)  .. (237bp,7.4983bp) .. controls (224.85bp,9.8374bp) and (212.04bp,14.613bp)  .. node[auto,near start] {$b$} (q6);
  \draw [->] (q0) ..controls (47.643bp,24.415bp) and (64.2bp,20.964bp)  .. (79bp,19.498bp) .. controls (94.922bp,17.922bp) and (99.078bp,17.922bp)  .. (115bp,19.498bp) .. controls (125.98bp,20.586bp) and (137.94bp,22.768bp)  .. node[auto,below] {$b$} (q6);
  \draw [->] (q2) ..controls (124.28bp,51.26bp) and (137.94bp,45.936bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q8) ..controls (234.03bp,34.749bp) and (226.51bp,30.579bp)  .. (219bp,28.498bp) .. controls (214.15bp,27.154bp) and (208.87bp,26.751bp)  .. node[auto,near start] {$b$} (q6);
  \draw [->] (q6) ..controls (198.21bp,42.911bp) and (205.25bp,45.859bp)  .. (212bp,47.498bp) .. controls (216.59bp,48.613bp) and (221.55bp,49.292bp)  .. node[auto] {$a$} (q8);
%
\end{tikzpicture}

%%% end ex3p1b %%%
\end{center}

Les états $0,2,8,11$ sont finaux car ce sont eux qui ont $13$ dans
leur ε-fermeture.

(3) L'automate ainsi obtenu est déjà déterministe incomplet ; pour le
déterminiser-compléter, il n'y a qu'à ajouter un puits $\bot$ avec la
seule transition qui manque, c'est-à-dire une transition étiquetée par
$b$ depuis l'état $6$ (et des transitions de $\bot$ vers lui-même
étiquetées $a$ et $b$).  Nous ne représentons pas l'automate à $6$
états ainsi fabriqué.

(4) On part de l'algorithme déterministe complet obtenu à la
question (3), et on lui applique l'algorithme de minimisation.  On
sépare d'abord ses états en deux classes, les finaux $\{0,2,8,11\}$ et
les non-finaux $\{6,\bot\}$.  La transition étiquetée $a$ sépare les
états $6$ et $\bot$ car le premier aboutit dans la classe
$\{0,2,8,11\}$ tandis que le second aboutit dans la classe
$\{6,\bot\}$.  On vérifie ensuite qu'aucune transition ne sépare des
états.  L'automate minimal est donc le suivant :
\begin{center}
%%% begin ex3p1c %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q6) at (97bp,20.28bp) [draw,circle,state] {$6$};
  \node (qbot) at (176bp,20.28bp) [draw,circle,state] {$\bot$};
  \node (qF) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$F$};
  \draw [->] (q6) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$a$} (qF);
  \draw [->] (q6) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$b$} (qbot);
  \draw [->] (qbot) to[loop above] node[auto] {$a,b$} (qbot);
  \draw [->] (qF) to[loop above] node[auto] {$a$} (qF);
  \draw [->] (qF) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q6);
%
\end{tikzpicture}

%%% end ex3p1c %%%
\end{center}
où l'état $F$ représente la classe $0\equiv 2\equiv 8\equiv 11$.

(5) Il s'agit du langage constitué des mots n'ayant jamais deux $b$
consécutifs ni de $b$ final,
c'est-à-dire des mots dans lesquels chaque $b$ est suivi
d'au moins un $a$ : l'expression rationnelle initiale le présente
comme le langage constitués des mots formés d'un nombre quelconque de
$a$ puis d'un nombre quelconque de répétitions d'un $b$ suivi d'au
moins un $a$.  L'automate final interdit les suites de deux $b$
consécutifs comme ceci : l'état $F$ correspond à la situation où on ne
vient pas de rencontrer un $b$ (=la lettre précédente était un $a$ ou
bien on vient de commencer le mot) et on n'en a jamais rencontré deux,
l'état $6$ à la situation où on vient de rencontrer un $b$ et on n'en
a jamais rencontré deux, et l'état $\bot$ à la situation où on a
rencontré au moins une fois deux $b$ consécutifs.  Avec cette
description, il est clair que l'automate fait ce qui était demandé.
\end{corrige}


%
%
%

\exercice

Donner plusieurs (au moins trois) expressions rationnelles
équivalentes dénotant le langage reconnu par l'automate suivant sur
l'alphabet $\Sigma = \{a,b\}$ :

\begin{center}
%%% begin ex3p2 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,initial above,accepting below] {$0$};
  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$b$} (q0);
  \draw [->] (q2) to[loop right] node[auto] {$b$} (q2);
  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q0) to[loop left] node[auto] {$a$} (q0);
  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q1);
  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$a$} (q2);
%
\end{tikzpicture}


%%% end ex3p2 %%%
\end{center}
(On pourra considérer les ordres suivants d'élimination des états :
$2,1,0$, $1,2,0$ et $0,2,1$.)

\begin{corrige}
Si on commence par éliminer l'état $2$ (en considérant l'automate
comme un automate à transitions étiquetées par des expressions
rationnelles), l'état $1$ reçoit une transition vers lui-même
étiquetée $ab{*}a$.  Si on élimine l'état $1$, l'état $0$ reçoit à la
place une transition vers lui-même étiquetée par $b(ab{*}a){*}b$,
qu'on peut fusionner avec la transition vers lui-même déjà existante
étiquetée par $a$ pour une seule étiquetée par $a|b(ab{*}a){*}b$.
Quitte éventuellement à ajouter un nouvel état initial (conduisant à
$0$ par une transition spontanée) et un nouvel état final (vers lequel
$0$ conduit par une transition spontanée) et à éliminer n'état $0$, on
obtient finalement l'expression rationnelle
\[
(a|b(ab{*}a){*}b){*}
\]

Si on commence par éliminer l'état $1$, il apparaît une transition
$0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut
appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas
de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter
par $\bot$, symbole d'expression rationnelle qui dénote le lagange
vide, et l'expression rationnelle $\bot{*}$ est équivalente
à $\varepsilon$) ; mais il ne faut pas oublier que l'état $2$ reçoit
lui aussi une transition vers lui-même (en passant par $1$) étiquetée
$aa$, qu'on peut fusionner avec la transition vers lui-même déjà
existante étiquetée par $b$ pour obtenir une transition étiquetée
$b|aa$.  L'élimination de l'état $2$ fait alors apparaître une
transition de $0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut
fusionner avec la transition vers lui-même déjà étiquetée par $a$ pour
une seule étiquetée par $a|b(a(b|aa){*}a){*}b$.  On obtient finalement
\[
(a|b(a(b|aa){*}a){*}b){*}
\]
(en particulier, cette expression est équivalente à celle obtenue
précédemment).

Si on préfère commencer par éliminer l'état $0$, il faut au préalable
ajouter un nouvel état initial $I$ (conduisant à $0$ par une
transition spontanée) et un nouvel état final $F$ (vers lequel $0$
conduit par une transition spontanée).  L'élimination de l'état $0$
fait apparaître une transition de $I$ vers $1$ étiquetée $a{*}b$, une
transition $1$ vers $F$ étiquetée $ba{*}$, et une transition de l'état
$1$ vers lui-même étiquetée $ba{*}b$, et enfin une transition de $I$
vers $F$ étiquetée $a{*}$.  L'élimination de l'état $2$ fait
apparaître une transition de $1$ vers lui-même étiquetée $ab{*}a$,
qu'on peut fusionner avec celle déjà existante étiquetée $ba{*}b$ pour
obtenir une transition $(ab{*}a|ba{*}b)$.  Finalement, l'élimination
de l'état $1$ done l'expression rationnelle
\[
a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*}
\]
(toujours équivalente aux précédentes).
\end{corrige}



%
%
%

\bigbreak
\centerline{\textbf{Calculabilité}}

\exercice

(1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  L'ensemble $L
= \{u^k : u\in\Sigma^*, k\geq 2\}$ des mots qui sont une puissance
$k$-ième pour un $k\geq 2$ est-il décidable ?  Semi-décidable ?

(2) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
programme (ou, si on préfère, de la $e$-ième machine de Turing),
exécuté sur l'entrée $42$, termine en au plus $10^{1000+e}$ étapes
est-il décidable ?  Semi-décidable ?

(3) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
programme (ou, si on préfère, de la $e$-ième machine de Turing),
exécuté sur l'entrée $42$, termine en temps fini est-il décidable ?
Semi-décidable ?  (On pourra montrer qu'on peut y ramener le problème
de l'arrêt.)

\begin{corrige}
(1) Si $w = u^k$ pour un certain $u\neq\varepsilon$, alors
  nécessairement $k\leq |w|$ puisque $|w|=k\cdot|u|$.  On dispose donc
  de l'algorithme suivant pour décider si $w\in L$ : si
  $w=\varepsilon$, retourner vrai immédiatement ; sinon, pour $k$
  allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$
  facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour
  $0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$
  commençant à la position $\ell i$) : s'ils sont tous égaux, renvoyer
  vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne,
  renvoyer faux.  Le langage proposé est donc décidable (et \textit{a
    fortiori} semi-décidable).

(2) Donné un $e \in \mathbb{N}$, la fonction $10^{1000+e}$ est
  évidemment calculable.  On peut ensuite lancer l'exécution du
  $e$-ième programme, sur l'entrée $42$, pour au plus ce nombre
  d'étapes (en utilisant la machine universelle, c'est-à-dire, par
  exemple, en simulant la $e$-ième machine de Turing sur une machine
  de Turing).  Si l'exécution termine en le temps imparti, on renvoie
  vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé
  est bien décidable (et \textit{a fortiori} semi-décidable).

(3) L'ensemble $A$ proposé est « presque » le problème de l'arrêt.  La
  différence est que le problème de l'arrêt est l'ensemble des couples
  $(e,n)$ tels que le $e$-ième programme termine sur l'entrée $n$
  alors qu'ici on a fixé l'entrée à $42$.  Il s'agit donc de montrer
  que cette limitation ne rend pas pour autant calculable l'ensemble
  considéré.  Or donnés deux entiers $(e,n)$, on peut fabriquer un
  programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette
  valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus
  un tel $e'$ se calcule algorithmiquement à partir de $e$ et $n$.
  L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle
  autre entrée) se comporte donc comme l'exécution du programme $e$
  sur l'entrée $n$, et notamment, termine si et seulement si elle
  termine.  Autrement dit, $e'$ appartient à l'ensemble $A$ considéré
  dans cette question si et seulement si $(e,n)$ appartient au
  problème de l'arrêt.  Comme on vient de dire qu'on peut calculer
  $e'$ algorithmiquement à partir de $(e,n)$, si l'ensemble $A$ était
  décidable, le problème de l'arrêt le serait, ce qui n'est pas le
  cas.  Donc $A$ n'est pas décidable.  En revanche, $A$ est
  semi-décidable : il suffit de lancer l'exécution du programme $e$
  sur l'entrée $42$ et renvoyer vrai si ele termine (si elle ne
  termine pas, on ne termine pas).
\end{corrige}


%
%
%

\exercice

Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  On s'intéresse à
des langages sur $\Sigma$.

(A) Montrer que si deux langages $L_1$ et $L_2$ sont décidables, alors
$L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont décidables ; montrer
que si un langage $L$ est décidable alors $L^*$ est décidable (pour ce
dernier, on pourra commencer par chercher, si $w \in \Sigma^*$ est un
mot de longueur $n$, comment énumérer toutes les façons de le
factoriser en mots de longueur non nulle).

(B) Montrer que si deux langages $L_1$ et $L_2$ sont semi-décidables,
alors $L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont
semi-décidables ; montrer que si un langage $L$ est décidable alors
$L^*$ est semi-décidable.

\begin{corrige}
(A) Supposons qu'on dispose d'algorithmes $T_1$ et $T_2$ qui décident
  $L_1$ et $L_2$ respectivement (i.e., donné $w \in \Sigma^*$,
  l'algorithme $T_i$ termine toujours en temps fini, en répondant oui
  si $w\in L_i$ et non si $w\not\in L_i$).

Pour faire un algorithme qui décide $L_1\cup L_2$, donné un mot
$w\in\Sigma^*$, il suffit de lancer successivement $T_1$ et $T_2$ : si
l'un des deux répond oui, on répond oui, sinon on répond non
(autrement dit, on calcule les valeurs de vérité de $w\in L_1$ et
$w\in L_2$ au moyen de $T_1$ et $T_2$, et on calcule ensuite leur
« ou » logique).  De même pour décider $L_1\cap L_2$, il suffit de
lancer successivement $T_1$ et $T_2$, si les deux répondent oui on
répond oui, sinon on répond non (i.e., on calcule les valeurs de
vérité de $w\in L_1$ et $w\in L_2$ au moyen de $T_1$ et $T_2$, et on
calcule ensuite leur « et » logique).

Pour décider $L_1 L_2$, on effectue une boucle sur toutes les
factorisation $w = uv$ de $w$, c'est-à-dire, une boucle sur toutes les
longueurs $0\leq i\leq |w|$ en appelant à chaque fois $u$ le préfixe
de $w$ de longueur $i$ et $v$ le suffixe de $w$ de longueur $|w|-i$,
et pour chaque paire $(u,v)$ ainsi trouvée, on utilise $T_1$ et $T_2$
pour tester si $u\in L_1$ et $v\in L_2$ : si c'est le cas, on termine
l'algorithme en répondant oui (on a $w = uv \in L_1 L_2$) ; si aucune
paire ne convient, on répond non.

L'algorithme pour décider $L^*$ est semblable : il s'agit de tester
toutes les manières de factoriser un mot $w \in \Sigma^*$ en facteurs
de longueur non nulle.  (On peut d'ores et déjà exclure
$w=\varepsilon$ car le mot vide appartient de toute façon à $L^*$.)
Si $n=|w| > 0$, on peut effectuer une boucle pour un nombre de
facteurs $k$ allant de $1$ à $n$, et, pour chaque $k$, effectuer $k$
boucles emboîtées pour déterminer les limites des facteurs
$u_1,\ldots,u_k \in \Sigma^+$ tels que $w = u_1\cdots u_k$ (il suffit
par exemple de faire boucler $i_1,\ldots,i_k$ chacun de $1$ à $n$, et
lorsque $i_1+\cdots+i_k = n$, appaler $u_j$ le facteur de $w$ de
longueur $i_j$ commençant à la position $i_1+\cdots+i_{j-1}$).  Pour
chaque factorisation comme on vient de le dire, on teste si tous les
$u_i$ appartiennent à $L$, et si c'est le cas on renvoie vrai (le mot
$w$ appartient à $L^*$) ; si aucune factorisation ne convient, on
renvoie faux.

(Dans l'algorithme qui précède, on a écarté les factorisations faisant
intervenir le mot vide, car si $w$ est factorisable en mots de $L$ en
faisant intervenir le mot vide, quitte à retirer celui-ci, il est
encore factorisable en mots non vides de $L$.)

(B) Les algorithmes sont très semblables à ceux de la partie (A) si ce
n'est qu'il faut tenir compte de la possibilité qu'ils puissent ne pas
terminer.  On doit donc les lancer « en parallèle » et pas « en
  série » : lorsqu'on dira qu'on lance deux algorithmes $T$ et $T'$
« en parallèle », cela signifie qu'on exécute une étape du calcul de
$T$, puis une étape de $T'$, puis de nouveau une de $T$, et ainsi de
suite en alternant entre les deux, jusqu'à ce que l'un termine et
renvoie vrai.

Si $L_1$ et $L_2$ sont semi-dédicables et si $T_1$ et $T_2$ sont des
algorithmes qui les « semi-décident » (i.e., $T_i$ termine en temps
fini et répond oui si $w\in L_i$, et ne termine pas sinon), pour
semi-décider $L_1\cup L_2$, on lance les deux algorithmes $T_1$ et
$T_2$ en parallèle sur le même mot $w$ : si l'un d'eux termine, on
termine en renvoyant vrai (sinon, bien sûr, on ne termine pas).

Pour semi-décider $L_1\cap L_2$, en revanche, il n'y a pas de raison
de procéder en parallèle : on lance d'abord $T_1$ sur le mot $w$ à
tester : si $T_1$ termine, on lance ensuite $T_1$ sur le même mot : si
$T_2$ termine et renvoie vrai, on renvoie vrai ; si l'un des deux
algorithmes $T_i$ lancés séquentiellement ne termine pas, bien sûr, le
calcul dans son ensemble ne terminera pas.

Pour semi-décider $L_1 L_2$ ou $L^*$, on procède comme dans le cas (A)
en lançant en parallèle les algorithmes pour tester toutes les
différentes factorisations possibles $w = uv$ ou bien $w = u_1\cdots
u_k$ (en mots non vides) du mot $w$.
\end{corrige}

%
%
%

\exercice

On rappelle qu'une fonction $f\colon \mathbb{N} \to \mathbb{N}$ est
dite \emph{calculable} lorsqu'il existe un algorithme (par exemple, un
programme pour une machine de Turing) prenant en entrée un
$n\in\mathbb{N}$ qui termine toujours en temps fini et renvoie la
valeur $f(n)$.  On rappelle qu'une partie $E$ de $\mathbb{N}$ ou de
$\mathbb{N}^2$ est dite \emph{décidable} lorsque sa fonction
indicatrice est calculable, ou, ce qui revient au même, lorsqu'il
existe un algorithme prenant en entrée un élément de $\mathbb{N}$ ou
de $\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
vrai ($1$) ou faux ($0$) selon que l'élément fourni appartient ou non
à $E$.  On rappelle enfin qu'une partie $E$ de $\mathbb{N}$ ou de
$\mathbb{N}^2$ est dite \emph{semi-décidable} lorsqu'il existe un
algorithme prenant en entrée un élément de $\mathbb{N}$ ou de
$\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
vrai ($1$) si l'élément fourni appartient à $E$, et sinon ne termine
pas (on peut aussi accepter qu'il termine en renvoyant faux, cela ne
change rien).

Soit $f\colon \mathbb{N} \to \mathbb{N}$ : montrer qu'il y a
équivalence entre les affirmations suivantes :
\begin{enumerate}
\item la fonction $f$ est calculable,
\item le graphe $\Gamma_f := \{(n,f(n)) : n\in\mathbb{N}^2\} =
  \{(n,p)\in\mathbb{N}^2 : p=f(n)\}$ de $f$ est décidable,
\item le graphe $\Gamma_f$ de $f$ est semi-décidable.
\end{enumerate}

(Montrer que (3) implique (1) est le plus difficile : on pourra
commencer par s'entraîner en montrant que (2) implique (1).  Pour
montrer que (3) implique (2), on pourra chercher une façon de tester
en parallèle un nombre croissant de valeurs de $p$ de manière à
s'arrêter si l'une quelconque convient.)

\begin{corrige}
Montrons que (1) implique (2) : si on dispose d'un algorithme capable
de calculer $f(n)$ en fonction de $n$, alors il est facile d'écrire un
algorithme capable de décider si $p=f(n)$ (il suffit de calculer
$f(n)$ avec l'algorithme supposé exister, de comparer avec la valeur
de $p$ fournie, et de renvoyer vrai/$1$ si elles sont égales, et
faux/$0$ sinon).

Le fait que (2) implique (3) est évident car tout ensemble décidable
est semi-décidable.

Montrons que (2) implique (1) même si ce ne sera au final pas utile :
supposons qu'on ait un algorithme $T$ qui décide $\Gamma_f$ (i.e.,
donnés $(n,p)$, termine toujours en temps fini, en répondant oui si
$p=f(n)$ et non si $p\neq f(n)$), et on cherche à écrire un algorithme
qui calcule $f(n)$.  Pour cela, donné un $n$, il suffit de lancer
l'algorithme $T$ successivement sur les valeurs $(n,0)$ puis $(n,1)$
puis $(n,2)$ et ainsi de suite (c'est-à-dire faire une boucle infinie
sur $p$ et lancer $T$ sur chaque couple $(n,p)$) jusqu'à trouver un
$p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la
valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition
de $T$.

Reste à montrer que (3) implique (1) : supposons qu'on ait un
algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$,
termine en temps fini et répond oui si $p=f(n)$, et ne termine pas
sinon), et on cherche à écrire un algorithme qui calcule $f(n)$.  Pour
cela, on va tester les valeurs $0\leq p\leq M$ chacune pour $M$ étapes
et faire tendre $M$ vers l'infini : plus exactement, on utilise
l'algorithme $U$ suivant :
\begin{itemize}
\item pour $M$ allant de $0$ à l'infini,
\begin{itemize}
\item pour $p$ allant de $0$ à $M$,
\begin{itemize}
\item exécuter l'algorithme $T$ sur l'entrée $(n,p)$ pendant au
  plus $M$ étapes,
\item s'il termine en renvoyant vrai ($1$), terminer et renvoyer $p$
  (sinon, continuer les boucles).
\end{itemize}
\end{itemize}
\end{itemize}

(Intuitivement, $U$ essaie de lancer l'algorithme $T$ sur un nombre de
valeurs de $p$ de plus en plus grand et en attendant de plus en plus
longtemps pour voir si l'une d'elles termine.)

Si l'algorithme $U$ défini ci-dessus termine, il renvoie forcément
$f(n)$ (puisque l'algorithme $T$ a répondu vrai, c'est que $p=f(n)$,
et on renvoie la valeur en question) ; il reste à expliquer pourquoi
$U$ termine toujours.  Mais la valeur $f(n)$ existe (même si on ne la
connaît pas) car la fonction $f$ était supposée définie partout, et
lorsque l'algorithme $T$ est lancé sur $(n,f(n))$ il est donc censé
terminer en un certain nombre (fini !) d'étapes : si $M$ est supérieur
à la fois à $f(n)$ et à ce nombre d'étapes, la valeur $f(n)$ va être
prise par $p$ dans la boucle intérieure, et pour cette valeur,
l'algorithme $T$ va terminer sur l'entrée $(n,p)$ en au plus $M$
étapes, ce qui assure que $U$ termine effectivement.

L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui
prouve (1).
\end{corrige}

%
%
%

\exercice

Soit $A \subseteq \mathbb{N}$ un ensemble infini.  Montrer qu'il y a
équivalence entre :
\begin{itemize}
\item l'ensemble $A$ est décidable,
\item il existe une fonction calculable \emph{strictement croissante}
  $f\colon\mathbb{N}\to\mathbb{N}$ telle que $f(\mathbb{N}) = A$.
\end{itemize}

\begin{corrige}
Supposons $A$ décidable : on va construire $f$ comme indiqué.  Plus
exactement, on va appeler $f(n)$ le $n$-ième élément de $A$ par ordre
croissant (c'est-à-dire que $f(0)$ est le plus petit élément de $A$,
et $f(1)$ le suivant par ordre de taille, et ainsi de suite ; noter
que $A$ est infini donc cette fonction est bien définie).  Montrons
que $f$ est calculable : donné un entier $n$, on teste successivement
si $0\in A$ puis $1\in A$ puis $2\in A$ et ainsi de suite, à chaque
fois en utilisant un algorithme décidant $A$ (qui est censé exister
par hypothèse) jusqu'à obtenir $n$ fois la réponse « oui » ; plus
exactement :
\begin{itemize}
\item initialiser $m \leftarrow 0$,
\item pour $k$ allant de $0$ à l'infini,
\begin{itemize}
\item interroger l'algorithme qui décide si $k\in A$,
\item s'il répond « oui » :
\begin{itemize}
\item si $m=n$, terminer et renvoyer $k$,
\item sinon, incrémenter $m$ (c'est-à-dire faire $m \leftarrow m+1$).
\end{itemize}
\end{itemize}
\end{itemize}
La boucle termine car $A$ est infini.

Réciproquement, supposons $f$ strictement croissante calculable et
posons $A = f(\mathbb{N})$ : on veut montrer que $A$ est décidable.
Or pour décider si $k \in A$, il suffit de calculer successivement
$f(0)$, $f(1)$, $f(2)$ et ainsi de suite, et de terminer si $f(n)$
atteint ou dépasse le $k$ fixé : s'il l'atteint, on renvoie vrai (on a
trouvé $n$ tel que $f(n)=k$), sinon, on renvoie faux (la valeur $k$ a
été sautée par la fonction $f$ et ne sera donc jamais atteinte).
L'algorithme est donc explicitement :
\begin{itemize}
\item pour $n$ allant de $0$ à l'infini,
\begin{itemize}
\item calculer $f(n)$,
\item si $f(n) = k$, renvoyer vrai,
\item si $f(n) > k$, renvoyer faux.
\end{itemize}
\end{itemize}
La boucle termine car toute fonction strictement croissante
$\mathbb{N}\to\mathbb{N}$ est de limite $+\infty$ en l'infini (donc
$f(n)$ finit forcément par atteindre ou dépasser $k$).
\end{corrige}

%
%
%

\exercice

Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième programme
(ou, si on préfère, de la $e$-ième machine de Turing) quand on lui
fournit le nombre $n$ en entrée, à supposer que cette exécution
termine ; sinon, $S(e,n)$ n'est pas défini.

Soit par ailleurs $M(k)$ le maximum des $S(e,n)$ pour $0\leq e\leq k$
et $0\leq n\leq k$ qui soient définis (et $0$ si aucun d'eux n'est
défini).  Autrement dit, il s'agit du plus petit entier supérieur ou
égal au nombre d'étapes de l'exécution de l'un des programmes $0\leq
e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils
terminent.

Montrer que la fonction $M$ n'est pas calculable (i.e., n'est pas
calculable par un algorithme) : on pourra pour cela montrer que la
connaissance de $M$ permet de résoudre le problème de l'arrêt.
Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq
M(k)$ pour tout $k$ n'est calculable.  Montrer que même si $M'$
vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est
pas calculable.

\emph{Remarque :} La fonction $M$, ou différentes variantes de
celle-ci, s'appelle fonction du « castor affairé ».  On peut montrer
encore plus fort : si $F$ est une fonction calculable quelconque,
alors il existe $k_0$ tel que $M(k) \geq F(k)$ pour $k\geq k_0$
(autrement dit, la fonction $M$ finit par dépasser n'importe quelle
fonction calculable : Radó, 1962, \textit{On Non-Computable
  Functions}).

\begin{corrige}
Supposons que $M$ soit calculable.  On peut alors résoudre le problème
de l'arrêt de la manière suivante : donné un algorithme $T$, de
numéro $e$, et une entrée $n$ à fournir à cet algorithme, pour savoir
si $T$ s'arrête, on calcule $M(k)$ où $k = \max(e,n)$, on exécute
ensuite l'algorithme $T$ pendant au plus $M(k)$ étapes : s'il termine
dans le temps imparti, on répond vrai (il a terminé), sinon, on répond
faux (il ne terminera jamais).  Cette résolution du problème de
l'arrêt est correcte, car si $T$ termine sur l'entrée $n$, il prendra
par définition $S(e,n)$ étapes, avec $0\leq e\leq k$ et $0\leq n\leq
k$ par définition de $k$, donc $S(e,n) \leq M(k)$ par définition de
$M(k)$ : ceci signifie précisément que si $T$ n'a pas terminé en
$M(k)$ étapes, il ne terminera jamais.

Exactement le même argument montre que $M'$ n'est pas calculable sous
l'hypothèse que $M'(k) \geq M(k)$ pour tout $k$ : s'il l'était, on
pourrait exécuter l'algorithme $T$ pendant au plus $M'(k)$ étapes, et
comme on a $S(e,n) \leq M(k) \leq M'(k)$, la même démonstration
convient.

Enfin, si on suppose seulement $M'(k)\geq M(k)$ pour $k\geq k_0$, la
fonction $M'$ n'est toujours pas calculable : en effet, si on suppose
par l'absurde qu'elle l'est, la fonction $M''$ qui à $k$ associe
$M'(k)$ si $k\geq k_0$ et $M(k)$ sinon, serait encore calculable
puisqu'elle ne diffère de $M'$ qu'en un nombre fini de valeurs, or
changer la valeur en un point d'une fonction calculable donne toujours
une fonction calculable (même si on « ne connaît pas » la valeur à
changer, elle existe, donc l'algorithme modifié existe).  Mais d'après
le paragraphe précédent, $M''$ n'est pas calculable puisqu'elle est
partout supérieure ou égale à $M$.
\end{corrige}


%
%
%
\end{document}