summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-03-17 19:50:06 +0100
committerDavid A. Madore <david+git@madore.org>2017-03-17 19:50:06 +0100
commit87ded2fe9da0d6d139573d0ebc670c058e4dab6b (patch)
treef17d2d7b71bce75b48f63f63672c7c6eaa9db1ce
parentdc5f7673b6a8492c153cd4119ddc94c729868f31 (diff)
downloadinf105-87ded2fe9da0d6d139573d0ebc670c058e4dab6b.tar.gz
inf105-87ded2fe9da0d6d139573d0ebc670c058e4dab6b.tar.bz2
inf105-87ded2fe9da0d6d139573d0ebc670c058e4dab6b.zip
Final exercise (computability).
-rw-r--r--controle-20170330.tex72
1 files changed, 69 insertions, 3 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex
index 1c50166..db38fc7 100644
--- a/controle-20170330.tex
+++ b/controle-20170330.tex
@@ -34,6 +34,7 @@
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
%
\DeclareFontFamily{U}{manual}{}
@@ -107,12 +108,13 @@ L'usage des appareils électroniques est interdit.
Durée : 1h30
-Barème \emph{indicatif} :
+Barème \emph{indicatif} : $8$ points pour chacun des deux premiers
+exercices, $4$ pour l'exercice 3.
\ifcorrige
-%Ce corrigé comporte 10 pages (page de garde incluse)
+%Ce corrigé comporte 7 pages (page de garde incluse)
\else
-%Cet énoncé comporte 4 pages (page de garde incluse)
+Cet énoncé comporte 3 pages (page de garde incluse)
\fi
\pagebreak
@@ -455,6 +457,70 @@ semi-décidable ?&oui&oui&oui&oui&oui\\
\end{corrige}
+%
+%
+%
+
+\exercice
+
+On rappelle que le \emph{problème de l'arrêt} $H$ est l'ensemble des
+couples $(e,x)$ formés d'un programme (=algorithme) $e$ et d'une
+entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$
+termine en temps fini (on peut éventuellement noter cela :
+$\varphi_e(x)\downarrow$). On rappelle que le problème de l'arrêt $H$
+est semi-décidable mais non décidable (autrement dit, on ne peut pas
+décider à l'avance en temps fini si un programme $e$ donné va terminer
+sur une entrée $x$, mais on peut au moins vérifier que c'est le cas
+quand ça l'est).
+
+On définit ici la variante $H'$ suivante du problème de l'arrêt : $H'$
+est l'ensemble des couples $(e,x)$ formés d'un programme $e$ et d'une
+entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$
+termine en temps fini et renvoie la réponse $42$ (si on veut :
+$\varphi_e(x) = 42$). Ainsi, on a $H' \subseteq H$ (ce fait est
+destiner à éclaircir la définition de $H'$ 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).
+
+\begin{corrige}
+(1) Le fait que $H'$ soit semi-décidable se montre de la même manière
+ que le fait que $H$ l'est : donnés un programme $e$ et une entrée
+ $x$, on lance l'exécution de $e$ sur l'entrée $x$ (au moyen, si on
+ veut être précis, d'une « machine universelle »), et si cette
+ exécution termine et renvoie la valeur $42$, on renvoie « vrai »,
+ sinon on rentre dans une boucle infinie (ou on renvoie « faux », peu
+ importe) ; bien sûr, si l'exécution de $e$ sur $x$ ne termine pas,
+ l'algorithme qu'on vient de décrire ne terminera pas non plus. Au
+ final, on a bien décrit un algorithme qui semi-décide $H'$.
+
+\smallbreak
+
+(2) 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$
+l'est aussi.
+
+Donnés un programme $e$ et une entrée $x$, on peut construire
+\emph{algorithmiquement} le programme $e'$ suivant : il effectue les
+mêmes opérations que $e$, mais, à la fin, ignore le résultat calculé,
+et renvoie toujours $42$. Ainsi, l'exécution de $e'$ sur l'entrée $x$
+termine et renvoie $42$ si et seulement si celle de $e$ sur cette même
+entrée termine (et renvoie n'importe quoi) : si on veut,
+$\varphi_{e'}(x)=42 \liff \varphi_e(x)\downarrow$. On peut alors
+utiliser $H'$ — supposé décidable — pour décider si $e'$ termine (sur
+l'entrée $x$) en renvoyant $42$ : comme ceci revient au même que de
+savoir si $e$ termine (sur l'entrée $x$), ceci fournit un moyen pour
+savoir si $e$ termine (sur l'entrée $x$). Autrement dit, on a résolu
+algorithmiquement le problème de l'arrêt, ce qui est une
+contradiction. C'est donc que $H'$ n'était, en fait, pas décidable.
+\end{corrige}
+
+
%
%