summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2018-03-16 19:07:41 (GMT)
committerDavid A. Madore <david+git@madore.org>2018-03-16 19:07:41 (GMT)
commit2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f (patch)
tree24917444e3562e618824fbc2faae47a56ab4aadd
parentc2bca8c28436f9c01abd2391f1ebb423b4357200 (diff)
downloadinf105-2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f.zip
inf105-2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f.tar.gz
inf105-2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f.tar.bz2
Answers to third exercise.
-rw-r--r--controle-20180322.tex58
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}
%
%