diff options
author | David A. Madore <david+git@madore.org> | 2018-03-16 20:07:41 +0100 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2018-03-16 20:07:41 +0100 |
commit | 2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f (patch) | |
tree | 24917444e3562e618824fbc2faae47a56ab4aadd | |
parent | c2bca8c28436f9c01abd2391f1ebb423b4357200 (diff) | |
download | inf105-2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f.tar.gz inf105-2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f.tar.bz2 inf105-2df9623ec9c5b2bb1bb750ca9ac37c52b161b72f.zip |
Answers to third exercise.
-rw-r--r-- | controle-20180322.tex | 58 |
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} % % |