Exercise showing that the indices of total functions is not semi-decidable nor co-semi-decidable.

1 files changed, 140 insertions, 0 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index 59fd82a..6a91072 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -252,6 +252,146 @@ grand on va finir par tester le couple $(n,i)$.)
 
 %
 
+\exercice\label{exercice-indices-fonctions-totales}\ (${\star}$)
+
+Soit
+\[
+T := \{e \in \mathbb{N} : \varphi^{(1)}_e\text{~est~totale}\}
+\]
+l'ensemble des codes des fonctions générales récursives totales
+(c'est-à-dire telles que $\forall
+n\in\mathbb{N}.\,(\varphi^{(1)}_e(n)\downarrow)$).  On se propose de
+montrer que ni $T$ ni son complémentaire $\complement T$ ne sont
+semi-décidables.
+
+\textbf{(1)} Montrer en guise d'échauffement que $T$ n'est pas
+décidable.
+
+\textbf{(2)} Soit $H := \{d \in \mathbb{N} :
+\varphi^{(1)}_d(0)\downarrow\}$ (variante du problème de l'arrêt).
+Rappeler brièvement pourquoi $H$ est semi-décidable mais non
+décidable, et pourquoi son complémentair $\complement H$ n'est pas
+semi-décidable.
+
+\textbf{(3)} Montrer qu'il existe une fonction $\rho \colon \mathbb{N}
+\to \mathbb{N}$ (totale) calculable (d'ailleurs même p.r.) telle que
+$\varphi^{(1)}_d(0)\downarrow$ si et seulement si
+$\varphi^{(1)}_{\rho(d)}$ est totale (\emph{indication :} on pourra
+par exemple construire un programme $e$ qui ignore son argument et qui
+simule $d$ sur l'entrée $0$).  Reformuler cette affirmation comme une
+réduction.  En déduire que le complémentaire $\complement T$ de $T$
+n'est pas semi-décidable.
+
+\textbf{(4)} Montrer qu'il existe une fonction $\sigma \colon
+\mathbb{N} \to \mathbb{N}$ (totale) calculable (d'ailleurs même p.r.)
+telle que $\varphi^{(1)}_d(0)\downarrow$ si et seulement si
+$\varphi^{(1)}_{\sigma(d)}$ \emph{n'est pas} totale
+(\emph{indication :} on pourra par exemple construire un programme $e$
+qui lance $d$ sur l'entrée $0$ pour un nombre d'étapes donné en
+argument, et fait une boucle infinie si cette exécution termine avant
+le temps imparti).  Reformuler cette affirmation comme une réduction.
+En déduire que $T$ n'est pas semi-décidable.
+
+\begin{corrige}
+On notera « $\varphi$ » pour « $\varphi^{(1)}$ » de manière à alléger
+les notations.
+
+\textbf{(1)} L'ensemble des fonctions calculables $\mathbb{N}
+\dasharrow \mathbb{N}$ qui sont en fait totales ($\mathbb{N} \to
+\mathbb{N}$) n'est ni vide (la fonction totale constante de valeur $0$
+est dedans) ni plein (la fonction nulle part définie n'est pas
+dedans).  D'après le théorème de Rice, l'ensemble $T$ des $e$ tels que
+$\varphi_e$ soit totale est indécidable : c'est exactement ce qui
+était demandé.
+
+\textbf{(2)} Toujours d'après le théorème de Rice, ou comme variante
+du problème de l'arrêt (qui s'y ramène par le théorème s-m-n),
+l'ensemble $H$ n'est pas décidable.  Il est cependant semi-décidable
+par universalité (on peut lancer l'exécution de $e$ sur l'entrée $0$
+et, si elle termine, renvoyer « oui »).  On en déduit que $\complement
+H$ n'est pas semi-décidable (car si $H$ et $\complement H$ étaient
+semi-décidables, $H$ serait décidable, ce qu'il n'est pas).
+
+\textbf{(3)} Considérons la fonction $\rho$ qui prend en entrée un
+programme $d$ (supposé d'un argument) et renvoie le programme $e =:
+\rho(d)$ (toujours d'un argument) qui ignore son argument et exécute
+$d$ sur l'entrée $0$ : essentiellement par le théorème s-m-n, cette
+fonction $\rho$ est totale calculable (d'ailleurs même p.r.).  Par
+définition, on a $\varphi_{\rho(d)}(n) = \varphi_d(0)$ (rappelons que
+ceci signifie que chacun est défini ssi l'autre l'est et, le cas
+échéant, que ces valeurs sont égales).  Notamment, si
+$\varphi_d(0)\downarrow$, alors $\varphi_{\rho(d)}$ est totale (et
+constante !), tandis que si $\varphi_d(0)\uparrow$, alors
+$\varphi_{\rho(d)}$ n'est nulle part définie (donc certainement pas
+totale).
+
+Bref, on a construit $\rho\colon\mathbb{N}\to\mathbb{N}$ totale
+calculable telle que $d \in H$ si et seulement si $\rho(d) \in T$, ou,
+ce qui revient au même, $d \in \complement H$ si et seulement si
+$\rho(d) \in \complement T$.  En termes de réductions, ceci signifie
+$H \mathrel{\leq_\mathrm{m}} T$, ou, ce qui revient au même,
+$\complement H \mathrel{\leq_\mathrm{m}} \complement T$ (le symbole
+« $\mathrel{\leq_\mathrm{m}}$ » désignant la réduction many-to-one).
+Comme $\complement H$ n'est pas semi-décidable, $\complement T$ ne
+l'est pas non plus.
+
+\emph{Remarque :} On n'est pas obligé d'utiliser le terme de
+« réduction many-to-one » pour argumenter que $\complement T$ n'est
+pas semi-décidable : on peut simplement dire « supposant par l'absurde
+que $\complement T$ soit semi-décidable, on pourrait semi-décider
+$\complement H$ de la façon suivante : donné $d$, on calcule
+$\rho(d)$, on semi-décide si $\rho(d) \in \complement T$ et, si c'est
+le cas, on termine en renvoyant “oui” ; or ce n'est pas possible, d'où
+une contradiction ».
+
+\textbf{(4)} Considérons la fonction $\sigma$ qui prend en entrée un
+programme $d$ (supposé d'un argument) et renvoie le programme $e :=
+\sigma(d)$ (toujours d'un argument) défini ainsi : le programme $e$
+prend en entrée un nombre $n$ et exécute le programme $d$ sur l'entrée
+$0$ pendant $\leq n$ étapes (mettons que ce soient des machines de
+Turing, sinon remplacer cet argument par une recherche d'arbre de
+calcul parmi les entiers naturels de $0$ à $n$) : si cette exécution a
+terminé en $\leq n$ étapes, alors $d$ effectue une boucle infinie,
+sinon $d$ termine (et renvoie, disons, $1729$).
+
+Il n'y a pas de difficulté à coder ce programme $e$ (on rappelle
+qu'exécuter un programme donné sur $\leq n$ étapes est calculable,
+d'ailleurs même primitif récursif), et de plus la fonction $\sigma$
+transformant $d$ en $e$ est elle-même calculable (et d'ailleurs elle
+aussi primitive récursive).
+
+Par définition de $e := \sigma(d)$, la fonction $\varphi_e$ est :
+\begin{itemize}
+\item soit définie pour tout $n$ (et de valeur $1729$), ce qui se
+  produit exatement lorsque l'exécution de $d$ ne termine jamais,
+  i.e. $\varphi_d(0) \uparrow$,
+\item soit définie jusqu'en un certain $n$ et non définie après, ce
+  qui se produit exactement lorsque l'exécution de $d$ termine en un
+  certain nombre d'étapes, i.e. $\varphi_d(0) \downarrow$.
+\end{itemize}
+En particulier, si $\varphi_d(0)\uparrow$, alors $\varphi_{\sigma(d)}$
+est totale (et constante !), tandis que si $\varphi_d(0)\downarrow$,
+alors $\varphi_{\sigma(d)}$ n'est pas totale.
+
+Bref, on a construit $\sigma\colon\mathbb{N}\to\mathbb{N}$ totale
+calculable telle que $d \in H$ si et seulement si $\sigma(d) \not\in
+T$, ou, ce qui revient au même, $d \in \complement H$ si et seulement
+si $\sigma(d) \in T$.  En termes de réductions, ceci signifie
+$\complement H \mathrel{\leq_\mathrm{m}} T$.  Comme $\complement H$
+n'est pas semi-décidable, $T$ ne l'est pas non plus.
+
+\emph{Remarque :} Comme dans la question précédente, on n'est pas
+obligé d'utiliser le terme de « réduction many-to-one » pour
+argumenter que $T$ n'est pas semi-décidable : on peut simplement dire
+« supposant par l'absurde que $T$ soit semi-décidable, on pourrait
+semi-décider $\complement H$ de la façon suivante : donné $d$, on
+calcule $\sigma(d)$, on semi-décide si $\sigma(d) \in T$ et, si c'est
+le cas, on termine en renvoyant “oui” ; or ce n'est pas possible, d'où
+une contradiction ».
+\end{corrige}
+
+%
+
 \exercice\label{exercice-graphe-calculable}\ (${\star}{\star}$)
 
 Soit $f\colon \mathbb{N} \to \mathbb{N}$ une fonction totale : montrer