diff options
| -rw-r--r-- | controle-20170330.tex | 41 |
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$ |