From 2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 16 Mar 2018 20:07:41 +0100
Subject: Answers to third exercise.

---
 controle-20180322.tex | 58 ++++++++++++++++++++++++++++++++++++++++++++-------
 1 file 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}
 
 %
 %
-- 
cgit v1.2.3