summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-03-25 19:21:28 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-03-25 19:21:28 (GMT)
commitbdd449efcbd5692905b246ed948aa5be51e16aa2 (patch)
treebef32507180fd0af652a269da7c849f91bbda11e
parent4e92cf3bfa832965eefb3c4c3f8456cc98dd1f0e (diff)
downloadinf105-bdd449efcbd5692905b246ed948aa5be51e16aa2.zip
inf105-bdd449efcbd5692905b246ed948aa5be51e16aa2.tar.gz
inf105-bdd449efcbd5692905b246ed948aa5be51e16aa2.tar.bz2
Suggest two options on how to solve the last question.exam-20170330
-rw-r--r--controle-20170330.tex41
1 files changed, 38 insertions, 3 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex
index 7054af5..90fda16 100644
--- a/controle-20170330.tex
+++ b/controle-20170330.tex
@@ -482,8 +482,18 @@ mais n'est pas utile pour la suite).
(1) Montrer que $H'$ est semi-décidable.
-(2) Montrer que $H'$ n'est pas décidable : pour cela, on cherchera à
-montrer que s'il l'était, $H$ le serait aussi.
+(2) Montrer que $H'$ n'est pas décidable : pour cela, on pourra,
+\emph{au choix} :
+\begin{itemize}
+\item montrer directement que $H'$ n'est pas décidable, en imitant la
+ démonstration du cours que $H$ n'est pas décidable (on pourra
+ essayer de construire un programme qui contredit la prédiction faite
+ par $H'$ sur son comportement), \emph{ou bien}
+\item montrer que si $H'$ était décidable, $H$ le serait aussi, ce qui
+ constitue une contradiction (donné un programme $e$, on pourra
+ modifier celui-ci en un programme $e'$ de manière à rendre utile la
+ prédiction faite par $H'$ sur son comportement).
+\end{itemize}
\begin{corrige}
(1) Le fait que $H'$ soit semi-décidable se montre de la même manière
@@ -498,7 +508,32 @@ montrer que s'il l'était, $H$ le serait aussi.
\smallbreak
-(2) Supposons par l'absurde que $H'$ soit décidable (c'est-à-dire,
+(2) Donnons deux solutions, correspondant aux deux approches suggérées
+par l'énoncé.
+
+\emph{Première approche} (montrer directement que $H'$ n'est pas
+décidable) :
+
+Si $H'$ était décidable, on pourrait définir un algorithme qui, donné
+un programme $e$, effectue les calculs suivants : (1º) utiliser un
+algorithme décidant $H'$ (on a supposé qu'il en existe un) pour
+savoir, algorithmiquement en temps fini, si le programme $e$ termine
+et renvoie $42$ quand on lui passe son propre numéro $e$ en entrée, et
+(2º) si oui, terminer en renvoyant la valeur $43$ (disons), et si non,
+terminer en renvoyant $42$. L'algorithme qui vient d'être décrit
+correspond à un certain programme, disons, $p$, et la description de
+l'algorithme fait que, quelque soit $e$, la valeur renvoyée par $p$
+sur $e$ vaut $43$ si celle renvoyée par $e$ sur $e$ vaut $42$, et vaut
+$42$ sinon (y compris si $e$ ne termine pas sur l'entrée $e$). En
+particulier, en prenant $e=p$, on voit que la valeur renvoyée par $p$
+sur $p$ vaut $42$ si et seulement si elle ne vaut pas $42$, ce qui est
+une contradiction. C'est donc que $H'$ n'était, en fait, pas
+décidable.
+
+\emph{Seconde approche} (ramener l'indécidabilité de $H'$ à celle
+de $H$) :
+
+Supposons par l'absurde que $H'$ soit décidable (c'est-à-dire,
concrètement, qu'on dispose d'un moyen de savoir si un programme $e$,
quand on lui fournit une entrée $x$, termine en renvoyant la
valeur $42$) et montrons, pour arriver à une contradiction, que $H$