Answers to third exercise.

1 files changed, 51 insertions, 7 deletions

diff --git a/controle-20180322.tex b/controle-20180322.tex
index 20ef61e..a9d1e83 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -525,14 +525,37 @@ impossible.
 \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.
+(ou les erreurs) commise(s) par le raisonnement incorrect, et
+détailler les éventuels passages incomplets dans le raisonnement
+correct.
+
+\begin{corrige}
+C'est Hippolyte qui a raison ($L$ n'est pas semi-décidable).
+
+L'argument de Thésée est stupide : une instruction mettant fin au
+programme avec une valeur autre que $0$ pourrait ne jamais être
+atteinte, et réciproquement, même si toutes les instructions mettant
+fin au programme renvoyaient $0$, il pourrait aussi ne jamais
+terminer.  (Au passage, l'argument de Thésée semblerait même montrer
+que $L$ est décidable, pas juste semi-décidable.)
+
+L'argument d'Hippolyte, lui, est correct : il montre que si $L$ était
+semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble
+des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est
+pas le cas.  Parmi les points qui méritent éventuellement d'être
+préciser, on peut mentionner : le fait que $e$ se déduise
+algorithmiquement de $e'$ et $m$ ; et le fait qu'il est
+algorithmiquement possible de lancer l'exécution d'un programme sur
+$n$ étapes (peu importe la définition exacte de « étape » tant que
+chacune termine à coup sûr en temps fini) et tester si elle est bien
+finie au bout de ce temps.
+\end{corrige}
 
 \medskip
 
-(2) Achille et Patrocle se disputent pour savoir si $M$ est
-semi-décidable.  Achile pense qu'il l'est, et il tient le raisonnement
-suivant pour l'expliquer :
+(2) Achille et Patrocle se disputent pour savoir si $M$ (le
+complémentaire de $L$) est semi-décidable.  Achile pense qu'il l'est,
+et il tient le raisonnement suivant pour l'expliquer :
 
 {\narrower
 
@@ -566,8 +589,29 @@ problème de l'arrêt, ce qui est impossible.
 \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.
+(ou les erreurs) commise(s) par le raisonnement incorrect, et
+détailler les éventuels passages incomplets dans le raisonnement
+correct.
+
+\begin{corrige}
+C'est Patricle qui a raison ($M$ n'est pas semi-décidable).
+
+Le raisonnement d'Achille se fonde sur l'idée que le complémentaire de
+« l'ensemble des programmes qui renvoient toujours la valeur $0$ » est
+« l'ensemble des programmes qui renvoient parfois une valeur autre
+que $0$ », ce qui oublie la possibilité que le programme ne termine
+pas.  C'est là la principale erreur (le reste est globalement
+correct).
+
+L'argument de Patrocle, lui, est correct : il montre que si $M$ était
+semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble
+des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est
+pas le cas.  On fait appel à des fonctions constantes, et qui ne
+peuvent renvoyer que $0$ ou ne pas terminer, mais ce n'est pas
+spécialement problématique.  Parmi les points qui méritent
+éventuellement d'être préciser, on peut mentionner le fait que $e$ se
+déduise algorithmiquement de $e'$ et $m$.
+\end{corrige}
 
 %
 %