Third exercise.

1 files changed, 99 insertions, 0 deletions

diff --git a/controle-20180322.tex b/controle-20180322.tex
index a1eb15e..d06ec8d 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -184,4 +184,103 @@ de $b$).
 %
 %
 %
+
+\exercice
+
+Dans cet exercice, on s'intéresse au langage $L$ formé des
+programmes $e$ (codés, dans un langage Turing-complet fixé quelconque,
+comme des entiers naturels ou comme des mots sur un alphabet fixé sans
+importance) qui, quelle que soit le paramètre $n$ qu'on leur fournit
+en entrée, terminent en temps fini et retournent la valeur $0$ : soit
+$L = \{e : (\forall n) {\varphi_e(n)\downarrow} = 0\}$.  Si l'on
+préfère, $L$ est l'ensemble de toutes les façons de coder la fonction
+constante égale à $0$.  On appellera aussi $M$ le complémentaire
+de $L$.  On se demande si $L$ ou $M$ sont semi-décidables.
+
+\smallskip
+
+(1) Créon et Antigone se disputent pour savoir si $L$ est
+semi-décidable.  Créon pense qu'il l'est, et il tient le raisonnement
+suivant pour l'expliquer :
+
+{\narrower
+
+Pour savoir si un programme $e$ est dans l'ensemble $L$, il suffit de
+l'examiner pour vérifier que toutes les instructions qui mettent fin
+au programme renvoient la valeur $0$ : si c'est le cas, on termine en
+répondait « oui » (c'est-à-dire $e\in L$) ; sinon, on rentre dans une
+boucle infinie.  Ceci fournit un algorithme qui semi-décide $L$.
+
+\par}
+
+\smallskip
+
+\noindent Antigone, elle, pense que $L$ n'est pas semi-décidable.  Son
+argument est le suivant :
+
+{\narrower
+
+Si $L$ était semi-décidable, je pourrais m'en servir pour résoudre le
+problème de l'arrêt.  En effet, donné un programme $e'$ et une
+entrée $m$ sur laquelle je cherche à tester l'arrêt de $e'$, je peux
+fabriquer le programme $e$ qui prend une entrée $n$, lance l'exécution
+de $e'$ sur l'entrée $m$ pendant au plus $n$ étapes et à la fin
+renvoie $1$ si ces $n$ étapes ont suffi à terminer l'exécution
+de $e'$, et $0$ sinon.  Dire que $e \in L$ signifie que $e'$ ne
+termine jamais sur $m$, donc pouvoir semi-décider $L$ permet de
+résoudre algorithmiquement le problème de l'arrêt, ce qui est
+impossible.
+
+\par}
+
+\smallskip
+
+\noindent Qui a raison ?  Expliquer précisément quelle est l'erreur
+commise par le raisonnement incorrect, et détailler les éventuels
+passages incomplets dans le raisonnement correct.
+
+\medskip
+
+(2) Héloïse et Abélard se disputent pour savoir si $M$ est
+semi-décidable.  Héloïse pense qu'il l'est, et elle tient le
+raisonnement suivant pour l'expliquer :
+
+{\narrower
+
+Pour savoir si un programme $e$ est dans l'ensemble $M$, il suffit de
+tester successivement les valeurs $\varphi_e(n)$ pour tous les $n$
+possibles : si l'on rencontre un $n$ tel que $\varphi_e(n)$ n'est
+pas $0$, alors on termine en répondant « oui » (c'est-à-dire $e\in
+M$) ; sinon, on ne va jamais terminer, et cela signifie que $e\not\in
+M$.  Ceci fournit un algorithme qui semi-décide $M$.
+
+\par}
+
+\smallskip
+
+\noindent Abélard, lui, pense que $M$ n'est pas semi-décidable.  Son
+argument est le suivant :
+
+{\narrower
+
+Si $M$ était semi-décidable, je pourrais m'en servir pour résoudre le
+problème de l'arrêt.  En effet, donné un programme $e'$ et une
+entrée $m$ sur laquelle je cherche à tester l'arrêt de $e'$, je peux
+fabriquer le programme $e$ qui prend une entrée $n$, l'ignore purement
+et simplement, exécute $e'$ sur l'entrée $m$ et à la fin renvoie $0$.
+Dire que $e\in M$ signifie que $e'$ ne termine pas sur $m$, donc
+pouvoir semi-décider $M$ permet de résoudre algorithmiquement le
+problème de l'arrêt, ce qui est impossible.
+
+\par}
+
+\smallskip
+
+\noindent Qui a raison ?  Expliquer précisément quelle est l'erreur
+commise par le raisonnement incorrect, et détailler les éventuels
+passages incomplets dans le raisonnement correct.
+
+%
+%
+%
 \end{document}