More exercises on computability.

1 files changed, 250 insertions, 13 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index 26840c0..10149c1 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -71,7 +71,7 @@ Git: \input{vcline.tex}
 \section{Calculabilité}
 
 
-\exercice\ ($\star$)
+\exercice\ (${\star}$)
 
 On considère la fonction $f\colon \mathbb{N} \to \mathbb{N}$ qui à $n
 \in \mathbb{N}$ associe le $n$-ième chiffre de l'écriture décimale de
@@ -102,7 +102,25 @@ calculable.  Mieux : comme la boucle utilisée est bornée \textit{a
 
 %
 
-\exercice\label{exercice-image-calculable-est-semi-decidable}\ ($\star$)
+\exercice\ (${\star}$)
+
+Supposons que $A \subseteq B \subseteq \mathbb{N}$.  \textbf{(1)} Si
+$B$ est décidable, peut-on conclure que $A$ est décidable ?
+\textbf{(2)} Si $A$ est décidable, peut-on conclure que $B$ est
+décidable ?
+
+\begin{corrige}
+La réponse est non dans les deux cas : pour le voir appelons $H := \{e
+\in \mathbb{N} : \varphi_e(0)\downarrow\}$ (disons) : il est
+indécidable par une des variations du problème de l'arrêt (ou par le
+théorème de Rice).  Le fait que $H \subseteq \mathbb{N}$ avec
+$\mathbb{N}$ décidable réfute (1), et le fait que $\varnothing
+\subseteq H$ avec $\varnothing$ décidable réfute (2).
+\end{corrige}
+
+%
+
+\exercice\label{exercice-image-calculable-est-semi-decidable}\ (${\star}$)
 
 \textbf{(1)} Soit $f\colon \mathbb{N} \to \mathbb{N}$ totale
 calculable.  Montrer que l'image $f(\mathbb{N})$ (c'est-à-dire $\{f(i)
@@ -135,7 +153,27 @@ boucle potentiellement infinie comme une boucle pour $i$ allant de $0$
 
 %
 
-\exercice\label{exercice-image-fonction-partielle-calculable}\ ($\star\star$)
+\exercice\ (${\star}$)
+
+Montrer que l'ensemble des $e\in \mathbb{N}$ tels que
+$\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$ (rappel : ceci signifie que
+\emph{soit} $\varphi^{(1)}_e(0) \downarrow$ et $\varphi^{(1)}_e(1)
+\downarrow$ et $\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$, \emph{soit}
+$\varphi^{(1)}_e(0) \uparrow$ et $\varphi^{(1)}_e(1) \uparrow$) n'est
+pas décidable.
+
+\begin{corrige}
+L'ensemble $F$ des fonctions partielles calculables $f\colon
+\mathbb{N} \dasharrow \mathbb{N}$ telles que $f(0) = f(1)$ n'est ni
+vide (la fonction totale constante de valeur $0$ est dans $F$) ni
+plein (la fonction totale identité n'est pas dans $F$).  D'après le
+théorème de Rice, l'ensemble des $e$ tels que $\varphi^{(1)}_e \in F$
+est indécidable : c'est exactement ce qui était demandé.
+\end{corrige}
+
+%
+
+\exercice\label{exercice-image-fonction-partielle-calculable}\ (${\star}{\star}$)
 
 \textbf{(1)} Soit $B \subseteq \mathbb{N}$ semi-décidable et non-vide.
 Montrer qu'il existe $f\colon \mathbb{N} \to \mathbb{N}$ totale
@@ -214,7 +252,7 @@ grand on va finir par tester le couple $(n,i)$.)
 
 %
 
-\exercice\ ($\star\star$)
+\exercice\label{exercice-graphe-calculable}\ (${\star}{\star}$)
 
 Soit $f\colon \mathbb{N} \to \mathbb{N}$ une fonction totale : montrer
 qu'il y a équivalence entre les affirmations suivantes :
@@ -296,12 +334,70 @@ tester le couple $(n,q)$.)
 
 %
 
-\exercice\ ($\star\star\star$)
+\exercice\label{exercice-reconnaitre-fonctions-p-r}\ (${\star}{\star}$)
+
+Si $e \mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions
+primitives récursives en une variable (= d'arité $1$) et $e \mapsto
+\varphi^{(1)}_e$ celle des fonctions générales récursives en une
+variable, on considère les ensembles
+\[
+M := \{e \in \mathbb{N} : \psi^{(1)}_e\text{~définie}\}
+\]
+\[
+N := \{e \in \mathbb{N} : \exists
+e'\in\mathbb{N}.(\psi^{(1)}_{e'}\text{~définie~et~}\varphi^{(1)}_e =
+\psi^{(1)}_{e'})\}
+\]
+Expliquer informellement ce que signifient ces deux ensembles (en
+insistant sur le rapport entre eux), dire s'il y a une inclusion de
+l'un dans l'autre, et dire si l'un ou l'autre est décidable.
+
+\begin{corrige}
+L'ensemble $M$ est l'ensemble des codes valables de fonction
+primitives récursives, c'est-à-dire de codes légitimes dans le langage
+primitif récursif ; l'ensemble $N$ qui est $\{e \in \mathbb{N} :
+\varphi^{(1)}_e \text{~est~p.r.}\}$ est l'ensemble des codes de
+fonctions générales récursives qui s'avèrent être primitives
+récursives (même si ce n'est pas forcément manifeste sur le
+programme).  Si on préfère, $M$ est l'ensemble des \emph{intentions}
+primitives récursives, alors que $N$ est l'ensemble des intentions
+dont l'\emph{extension} est primitive récursive ; \textit{grosso
+  modo}, l'appartenance à $M$ se lit sur le code de la fonction, celle
+à $N$ se lit sur les valeurs de la fonction.
+
+Manifestement, $M \subseteq N$, car si $\psi^{(1)}_e$ est définie, on
+a $\varphi^{(1)}_e = \psi^{(1)}_e$ (la définition des fonctions
+générales récursives \emph{étend} celle des fonctions p.r.).
+L'inclusion dans l'autre sens ne vaut pas : on peut calculer la
+fonction constante nulle en faisant une boucle infinie, ce qui fournit
+un code $e$ tel que $\varphi^{(1)}_e$ est primitive récursive (donc
+$e\in N$) et pourtant $\psi^{(1)}_e$ n'est pas définie (donc $e\not\in
+M$).
+
+L'ensemble $M$ est décidable : on peut décider de façon algorithmique
+si $e$ est un numéro valable de fonction primitive récursive (i.e., si
+$\psi^{(1)}_e$ est définie), il s'agit pour cela simplement de
+« décoder » $e$ et de vérifier qu'il suit les conventions utilisées
+pour numéroter les fonctions primitives récursives (pour être très
+précis, le décodage termine parce que le code d'une liste est
+supérieur à tout élément de cette liste).
+
+L'ensemble $N$ n'est pas décidable : si $F$ désigne l'ensemble des
+fonctions p.r. $\mathbb{N} \to \mathbb{N}$ (c'est-à-dire l'image de
+$M$ par $e \mapsto \psi^{(1)}_e$), alors $N$ est $\{e\in\mathbb{N} :
+\varphi^{(1)}_e \in F\}$, et comme $F$ n'est ni vide ni l'ensemble de
+toutes les fonctions générales récursives, le théorème de Rice dit
+exactement que $N$ est indécidable.
+\end{corrige}
+
+%
+
+\exercice\label{exercice-diagonalisation-0-1-fonctions-p-r}\ (${\star}{\star}{\star}$)
 
 On considère la fonction $f\colon \mathbb{N}^2 \to \mathbb{N}$ qui à
 $(e,x)$ associe $1$ si $\psi^{(1)}_e(x) = 0$ et $0$ sinon (y compris
-si $\psi^{(1)}_e$ n'est pas définie), où $e \mapsto \psi^{(1)}$ est la
-numérotation standard des fonctions primitives récursives en une
+si $\psi^{(1)}_e$ n'est pas définie), où $e \mapsto \psi^{(1)}_e$ est
+la numérotation standard des fonctions primitives récursives en une
 variable (= d'arité $1$).
 
 La fonction $f$ est-elle calculable ?  Est-elle primitive récursive ?
@@ -313,12 +409,12 @@ dans $f$ ?
 La fonction $f$ est calculable.  En effet,
 \begin{itemize}
 \item on peut décider de façon algorithmique si $e$ est un numéro
-  valable de fonction primitive récursive (i.e., si $\psi^{(1)}_e$),
-  il s'agit pour cela simplement de « décoder » $e$ et de vérifier
-  qu'il suit les conventions utilisées pour numéroter les fonctions
-  primitives récursives (pour être bien précis, le décodage termine
-  parce que le code d'une liste est supérieur à tout élément de cette
-  liste) ;
+  valable de fonction primitive récursive (i.e., si $\psi^{(1)}_e$ est
+  définie), il s'agit pour cela simplement de « décoder » $e$ et de
+  vérifier qu'il suit les conventions utilisées pour numéroter les
+  fonctions primitives récursives (pour être très précis, le décodage
+  termine parce que le code d'une liste est supérieur à tout élément
+  de cette liste) ;
 \item lorsque c'est le cas, on peut calculer $\psi^{(1)}_e(x)$ car
   quand elle est définie elle coïncide avec $\varphi^{(1)}_e(x)$
   (numérotation des fonctions générales récursives), dont on sait
@@ -341,6 +437,147 @@ l'autre l'est), mais la démonstration ne se serait pas appliquée telle
 quelle.
 \end{corrige}
 
+%
+
+\exercice\ (${\star}{\star}{\star}$)
+
+Soit
+\[
+Z := \{e \in \mathbb{N} : \exists n \in \mathbb{N}.\, (\psi^{(1)}_e(n) = 0)\}
+\]
+l'ensemble des codes $e$ des fonctions p.r. $\mathbb{N} \to
+\mathbb{N}$ qui prennent (au moins une fois) la valeur $0$ (ici, $e
+\mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions
+primitives récursives en une variable).
+
+Montrer que $Z$ est semi-décidable.  Montrer qu'il n'est pas
+décidable.
+
+\begin{corrige}
+Comme dans le début du corrigé de
+l'exercice \ref{exercice-diagonalisation-0-1-fonctions-p-r}, on
+explique qu'on peut décider si $\psi^{(1)}_e(n)\downarrow$ (il s'agit
+juste de vérifier si $e$ est un code valable de fonction p.r.) et, une
+fois ce point vérifié, si $\psi^{(1)}_e(n) = 0$ (on peut calculer
+$\psi^{(1)}_e(n) = \varphi^{(1)}_e(n)$ par universalité des fonctions
+générales récursives).
+
+Dès lors, pour semi-décider si $e \in Z$, il suffit de faire une
+boucle infinie pour $n$ parcourant les entiers naturels, décider si
+$\psi^{(1)}_e(n) = 0$ pour chacun, et si l'un d'eux est effectivement
+nul, terminer et renvoyer « oui », sinon on continue la boucle.  Ceci
+montre que $Z$ est semi-décidable.
+
+Montrons qu'il n'est pas décidable : pour cela, on va ramener le
+problème de l'arrêt à $Z$.  C'est en fait essentiellement ce que fait
+le théorème de la forme normale de Kleene : en effet, considérons
+$(p,x)$ dont il s'agit de décider si $\varphi^{(1)}_p(x)\downarrow$ :
+d'après le théorème de la forme normale, ceci se produit si et
+seulement si il existe un (entier codant un) arbre de calcul $n$
+attestant que $\varphi^{(1)}_p(x)\downarrow$, ce qu'on écrit
+$T(n,p,\dbllangle x\dblrangle)$, où $T$ est un prédicat p.r.,
+c'est-à-dire qu'il s'écrit $t(n,p,\dbllangle x\dblrangle) = 0$ pour
+une certaine fonction p.r. $t$ (qui teste si $n$ code un arbre de
+calcul valable pour $\varphi^{(1)}_p(x)$ et renvoie $0$ si c'est le
+cas, $1$ sinon).  On a ainsi $\varphi^{(1)}_p(x)\downarrow$ ssi
+$\exists n\in\mathbb{N}.\, (t(n,p,\dbllangle x\dblrangle) = 0)$.
+Maintenant, d'après le théorème s-m-n, on peut calculer de façon
+p.r. en $p$ et $x$ le code $\rho(p,x)$ d'une fonction p.r. telle que
+$\psi^{(1)}_{\rho(p,x)}(n) = t(n,p,\dbllangle x\dblrangle)$, et
+d'après ce qui a été dit juste avant, on a $\rho(p,x) \in Z$,
+c'est-à-dire $\exists n\in\mathbb{N}.\, (t(n,p,\dbllangle x\dblrangle)
+= 0)$, se produit si et seulement si $\varphi^{(1)}_p(x)\downarrow$,
+c'est-à-dire $(p,x) \in \mathscr{H}$ (où $\mathscr{H} := \{(p,x) \in
+\mathbb{N}^2 : \varphi^{(1)}_p(x)\downarrow\}$ désigne le problème de
+l'arrêt).  Ceci constitue une réduction \textit{many-to-one} de
+$\mathscr{H}$ à $Z$, donc $Z$ ne peut pas être décidable : en effet,
+si $Z$ était décidable, pour tester si $(p,x) \in \mathscr{H}$ il
+suffirait de tester si $\rho(p,x) \in Z$, donc le problème de l'arrêt
+serait décidable, ce qui n'est pas le cas.
+
+(De nouveau, si on n'aime pas le théorème de la forme normale de
+Kleene, on peut faire ça avec des étapes de machine de Turing :
+appeler $t(n,p,x)$ la fonction qui renvoie $0$ si la machine de Turing
+codée par $p$ termine en $\leq n$ étapes à partir de la configuration
+initiale codée par $x$, et $1$ sinon : le reste du raisonnement est
+essentiellement identique.)
+\end{corrige}
+
+%
+
+%% \exercice\ (${\star}$)
+
+%% Montrer qu'il existe une machine de Turing qui, quand on la lance sur
+%% la configuration vierge (c'est-à-dire un ruban vierge et dans
+%% l'état $1$), termine après avoir écrit son propre programme sur sa
+%% bande\footnote{Par exemple avec la convention suivante : les
+%% instructions du programme $\delta \colon \{1,\ldots,m\} \times \{0,1\}
+%% \to \{0,\ldots,m\} \times \{0,1\} \times \{\texttt{L},\texttt{R}\}$
+%% sont écrites de la gauche vers la droite dans l'ordre $\delta(1,0)$,
+%% $\delta(1,1)$, $\delta(2,0)$, $\delta(2,1)$, etc., chacune étant
+%% écrite sous forme du nouvel état, du nouveau symbole, et de la
+%% direction codée par $\texttt{L}\mapsto 0, \texttt{R}\mapsto 1$, tous
+%% les trois en unaire séparés par des $0$.}
+
+%
+
+\exercice\ (${\star}{\star}$)
+
+Soit $f \colon\mathbb{N} \to \mathbb{N}$ une fonction calculable par
+une machine de Turing en \emph{complexité d'espace} primitive
+récursive : cela signifie qu'il existe $p \colon\mathbb{N} \to
+\mathbb{N}$ primitive récursive et une machine de Turing $\mathscr{M}$
+telle que si on lui présente $n \in \mathbb{N}$ en entrée (écrit avec
+les conventions usuelles, c'est-à-dire en unaire sur la bande), la
+machine s'arrête en temps fini en ayant écrit $f(n)$ sur la bande, et
+de plus le nombre de cases de la bande que la tête de lecture a
+parcourues est $\leq p(n)$ (c'est-à-dire que $\mathscr{M}$ a utilisé
+$\leq p(n)$ cellules mémoire pour faire le calcul).
+
+On veut montrer que $f$ elle-même est primitive récursive
+(c'est-à-dire qu'une fonction calculable en complexité d'espace
+p.r. est elle-même p.r., de la même manière qu'une fonction calculable
+en complexité en temps p.r. est elle-même p.r.).
+
+\textbf{(1)} Si $\mathscr{M}$ a $\leq m$ états, montrer que le calcul
+de $f(n)$ par $\mathscr{M}$ ne peut faire intervenir qu'au plus
+$m\times p(n)\times 2^{p(n)+n}$ configurations différentes (on rappelle
+qu'une \emph{configuration} est la donnée d'un état, d'une position de
+la tête, et de la valeur de chaque cellule du ruban).
+
+\textbf{(2)} En déduire que le calcul de $f(n)$ par $\mathscr{M}$
+termine en au plus $m\times p(n)\times 2^{p(n)+n}$ étapes
+(\textit{indication :} sinon le calcul bouclerait indéfiniment, et on
+a supposé que ce n'était pas le cas).
+
+\textbf{(3)} En déduire que $f$ est primitive récursive.
+
+\begin{corrige}
+\textbf{(1)} Une configuration de l'exécution de $\mathscr{M}$ est la
+donnée d'un état parmi au plus $m$, d'une position de la tête parmi au
+plus $p(n)$ (puisque la tête visite au plus ce nombre de cellules), et
+de la valeur de chaque cellule du ruban ; or au plus $p(n)+n$ cellules
+peuvent contenir un $1$ (à n'importe quel moment de l'exécution), car
+la tête n'en viiste qu'au plus $p(n)$ et au plus $n$ portent un $1$
+initialement : il y a donc au plus $2^{p(n)+n}$ configurations
+possibles du ruban, et au plus $m\times p(n)\times 2^{p(n)+n}$
+configurations de l'ensemble de la machine.
+
+\textbf{(2)} Si $\mathscr{M}$ retombe sur une configuration exacte
+qu'elle a déjà exécutée, elle exécutera de nouveau exactement les
+mêmes instructions et ne retombera indéfiniment sur cette
+configuration sans jamais finir.  Comme on a supposé que le calcul
+terminait, c'est qu'il doit parcourir des configurations toutes
+distinctes, donc termine en au plus $m\times p(n)\times 2^{p(n)+n}$
+étapes.
+
+\textbf{(3)} On vient de montrer que le calcul de $f$ par
+$\mathscr{M}$ es fait en temps au plus $m\times p(n)\times
+2^{p(n)+n}$.  Mais ceci est une fonction p.r. de $n$ (car $p$ l'est,
+et que $k \mapsto 2^k$ l'est, et que $m$ est une constante ici).  Donc
+$f$ est calculée en complexité en temps p.r., donc elle est elle-même
+p.r.
+\end{corrige}