diff options
| -rw-r--r-- | controle-20260126.tex | 157 |
1 files changed, 141 insertions, 16 deletions
diff --git a/controle-20260126.tex b/controle-20260126.tex index 109b334..617e33b 100644 --- a/controle-20260126.tex +++ b/controle-20260126.tex @@ -585,7 +585,7 @@ lorsque, pour chaque $0 \leq i < |w|$, le bit numéroté $i$ de $w$ vaut \item $0$ s'il existe un arbre de calcul (codé par un entier) $<|w|$ attestant $\varphi_i(0) = 0$, \item $1$ s'il existe un arbre de calcul (codé par un entier) $<|w|$ - attestant $\varphi_i(0) = v$, où $v\neq 0$, + attestant $\varphi_i(0) = r$, où $r\neq 0$, \item et arbitraire sinon \end{itemize} où $\varphi_i$ désigne la $i$-ième fonction générale récursive. @@ -597,7 +597,7 @@ changer la définition en : d'une bande représentant le nombre $0$, ou tout autre état initial fixé, peu importe).} en $<|w|$ étapes et renvoie $0$, \item $1$ si la $i$-ième machine de Turing termine en $<|w|$ - étapes et renvoie une valeur $v \neq 0$, + étapes et renvoie une valeur $r \neq 0$, \item et arbitraire sinon \end{itemize} (cela ne changera rien de substantiel aux raisonnements). @@ -616,6 +616,17 @@ trivialement vérifiée — vu que $|\varepsilon|=0$.) \textbf{(1)} Montrer que si $v \in \mathscr{K}$ et si $u$ est un préfixe de $v$. alors on a aussi $u \in \mathscr{K}$. +\begin{corrige} +Supposons que $u$ soit un préfixe de $v$ avec $v \in \mathscr{K}$. +Alors pour tout $i$ tel que $0\leq i < |u|$, le bit numéroté $i$ +de $u$ est aussi le bit numéroté $i$ de $v$, qui d'après les +conditions sur $v \in \mathscr{K}$, vaut $0$ (resp. $1$) s'il existe +un arbre de calcul $<|v|$ attestant $\varphi_i(0) = 0$ +(resp. $\varphi_i(0) \neq 0$), et à plus forte raison s'il existe un +arbre de calcul $<|u|$ l'attestant : ceci implique donc bien $u \in +\mathscr{K}$. +\end{corrige} + \medskip On dit que $\mathscr{K}$ est un \textbf{arbre} de mots @@ -625,19 +636,57 @@ les sommets sont les éléments de $\mathscr{K}$, avec une arête de $u$ à $v$ lorsque $u$ est un préfixe de $v$, est un arbre (infini) au sens de la théorie des graphes. Cette remarque n'est pas utile pour le présent exercice.} pour exprimer la propriété démontrée par cette -question (1). +question (1) (formellement, un arbre de mots binaires est une partie +$\mathscr{T} \subseteq \{0,1\}^*$ telle que si $v\in\mathscr{T}$ et +que $u$ est un préfixe de $v$, alors $u\in\mathscr{T}$). \medskip \textbf{(2)} Montrer que $\mathscr{K}$ est une partie \emph{décidable} (i.e., calculable) de $\{0,1\}^*$. +\begin{corrige} +On veut montrer qu'il existe un algorithme qui, donné un $w \in +\{0,1\}^*$, décide si $w \in \mathscr{K}$. Pour cela, il suffit de +parcourir les bits $0\leq i<|w|$ de $w$ et, pour chacun de tester si +la condition définissant $\mathscr{K}$ est vérifiée : on parcourt les +entiers $0\leq j<|w|$ et, pour chacun, on teste s'il s'agit du code +d'un arbre de calcul attestant $\varphi_i(0) = r$ pour un certain $r$, +et, si c'est le cas, on vérifie que le bit $w_i$ de $w$ vaut $0$ si +$r=0$ ou $1$ si $r\neq 0$. (Si on préfère les machines de Turing, on +lance l'exécution de la $i$-ième machine pour au plus $|w|-1$ étapes +et le reste est analogue.) Si une des conditions échoue, le mot $w$ +n'est pas dans $\mathscr{K}$, tandis que si toutes réussissent, le mot +est dans $\mathscr{K}$. Il s'agit bien là d'un algorithme qui termine +à coup sûr en temps fini (il est même primitif récursif puisqu'on a +essentiellement deux boucles imbriquées, une sur $i$ et une sur $j$, +bornées par $|w|$). +\end{corrige} + \medskip \textbf{(3)} Montrer qu'il existe dans $\mathscr{K}$ des mots binaires de longueur arbitrairement grande (formellement : $\forall n. \; \exists w\in\mathscr{K}. \; (|w| \geq n)$). On pourra même expliquer -comment en calculer algorithmiquement. +comment en calculer algorithmiquement un de longueur quelconque. + +\begin{corrige} +Comme on l'a expliqué à la question (2), la condition définissant +l'appartenance d'un mot à $w$ est testable algorithmiquement. Pour +fabriquer un mot de $\mathscr{K}$ de longueur $n$, on teste, pour +chaque $0\leq i<|w|$ s'il existe un arbre de calcul $<n$ attestant +$\varphi_i(0) = r$ pour un certain $r$ (ou, si on préfère, si +l'exécution de la $i$-ième machine pour au plus $n-1$ étapes termine +et renvoie une valeur $r$), et, si c'est le cas, on donne au bit +numéroté $i$ de $w$ la valeur imposée par ce $r$ (forcément unique, +puisqu'il s'agit da la valeur de $\varphi_i(0)$), sinon on lui donne +une valeur quelconque, disons $0$ : le mot formé des bits qu'on vient +de dire est dans $\mathscr{K}$ puisqu'il vérifie les contraintes. De +plus, on l'a calculé algorithmiquement. Il existe donc bien un mot de +longueur $n$ de $\mathscr{K}$ pour chaque $n$, et même un algorithme +qui en renvoie un en fonction de $n$. Ceci implique trivialement ce +qui était demandé. +\end{corrige} \medskip @@ -653,9 +702,10 @@ pour tout $\ell \in \mathbb{N}$. qu'il n'existe pas d'algorithme qui prend en entrée un $e \in \mathbb{N}$, \emph{termine toujours en temps fini}, et renvoie \begin{itemize} -\item $0$ si $\varphi_e(0) = 0$, -\item $1$ si $\varphi_e(0) = v$ où $v \neq 0$, -\item et une valeur arbitraire sinon. +\item $0$ si $\varphi_e(0){\downarrow} = 0$, +\item $1$ si $\varphi_e(0){\downarrow} = r$ où $r \neq 0$, +\item et une valeur arbitraire sinon (i.e., si $\varphi_e(0)$ n'est + pas définie). \end{itemize} \emph{Si on préfère} parler en termes de machines de Turing, on pourra montrer qu'il n'existe pas d'algorithme qui prend en entrée le code @@ -665,7 +715,7 @@ renvoie \item $0$ si la $e$-ième machine de Turing termine et qu'elle renvoie $0$, \item $1$ si la $e$-ième machine de Turing termine et qu'elle renvoie - une valeur $v \neq 0$, + une valeur $r \neq 0$, \item et une valeur arbitraire sinon. \end{itemize} @@ -677,25 +727,91 @@ précise : on ne se contentera pas d'un raisonnement informel du type « on ne peut pas savoir si $\varphi_e(0)$ terminera un jour, donc on ne peut pas calculer sa valeur ». +\begin{corrige} +Supposons par l'absurde qu'il existe un algorithme qui prend en +entrée $e$, termine toujours en temps fini et renvoie une valeur comme +indiqué dans la question ; appelons $f$ la fonction calculable que +calcule cet algorithme. On va aboutir à une contradiction. + +Considérons maintenant le programme $e$ défini comme suit. Il ignore +son argument, calcule $f(e)$ en vertu de l'algorithme dont on vient de +supposer l'existence, et renvoie $1$ si $f(e)=0$ et $0$ si $f(e)\neq +0$. L'astuce de Quine rend légitime l'utilisation de $e$ dans sa +propre définition (formellement : considère la fonction qui à $e$ +associe la fonction qu'on vient de dire, et on applique le théorème de +récursione de Kleene à cette fonction). Par construction, cet +algorithme termine toujours en temps fini (puisqu'on a supposé que +c'était le cas du calcul de $f$). Bref, $\varphi_e(n)$ est toujours +défini, et $\varphi_e(n) = 1$ si $f(e)=0$ et $\varphi_e(n) = 0$ si +$f(e) \neq 0$. + +Si $f(e)=0$ alors $\varphi_e(0) = 1$ comme on vient de le dire, donc +on a $f(e)=1$ par définition de la fonction $f$, ce qui est une +contradiction ; et si $f(e)\neq 0$ alors $\varphi_e(0) = 0$ comme on +vient de le dire, donc $f(e)=0$ par définition de la fonction $f$, ce +qui est de nouveau une contradiction. + +C'est donc que notre hypothèse (de calculabilité de $f$) était +absurde. +\end{corrige} + \medskip \textbf{(5)} Déduire de (4) qu'il n'existe aucune branche infinie calculable de $\mathscr{K}$. +\begin{corrige} +Si $(b_i)$ est une branche infinie de $\mathscr{K}$, vérifions que $e +\mapsto b_e$ vérifie les conditions du (4) (c'est-à-dire vaut $0$ si +$\varphi_e(0){\downarrow}=0$ et $r$ si $\varphi_e(0){\downarrow}\neq +0$). Supposons que $\varphi_e(0){\downarrow}$, mettons $\varphi_e(0) += r$ : alors il existe un arbre de calcul l'attestant, codé, disons, +par un entier $m$. Appelons $\ell = \max(m, e) + 1$. Le mot $w := +b_0\cdots b_{\ell-1}$ (de longueur $\ell > m$) est dans $\mathscr{K}$ +par l'hypothèse que $(b_i)$ est une branche de $\mathscr{K}$. Il +existe un arbre de calcul codé par un entier $<|w|$ (à savoir $m$) +attestant $\varphi_e(0) = r$, donc le bit $b_e$ de $w$ vaut $0$ +si $r=0$ et $1$ si $r\neq 0$. On a donc bien prouvé que $e \mapsto +b_e$ vérifie les conditions du (4). Or on a vu en (4) qu'une telle +fonction ne peut pas être calculable. C'est donc que $\mathscr{K}$ +n'a pas branche infinie calculable. +\end{corrige} + \medskip Le \textbf{lemme de Kőnig} est l'affirmation suivante : « tout arbre -de mots binaires contenant des mots binaires de longueur -arbitrairement grande a une branche infinie » (les termes « arbre », -« contenant des mots binaires de longueur arbitrairement grande » et -« branche infinie » ont été définis précisément ci-dessus). On ne -demande pas de démontrer cette affirmation : néanmoins, c'est un -théorème des mathématiques classiques usuelles. +de mots binaires contenant des mots de longueur arbitrairement grande +a une branche infinie » (les termes « arbre », « contenant des mots de +longueur arbitrairement grande » et « branche infinie » ont été +définis précisément ci-dessus). On ne demande pas de démontrer cette +affirmation : néanmoins, c'est un théorème des mathématiques +classiques usuelles. \medskip -\textbf{(6)} Que peut-on conclure du lemme de Kőnig concernant -l'arbre $\mathscr{K}$ ? +\textbf{(6)} Pour résumer, que peut-on conclure du lemme de Kőnig, et +des questions précédentes, concernant l'arbre $\mathscr{K}$ ? Comment +expliqueriez-vous informellement la situation ? + +\begin{corrige} +On a vu que $\mathscr{K}$ est un arbre de mots binaires calculable, +contenant des mots de longueur arbitrairement grande. Par le lemme de +Kőnig, il a des branches infinies. Néanmoins, aucune de ses branches +n'est calculable. + +On peut décrire informellement $\mathscr{K}$ comme un « labyrinthe +infini, calculable mais impossible à résoudre de façon calculable » : +les pièces du labyrinthe sont les nœuds de l'arbre, c'est-à-dire les +$w\in\mathscr{K}$, chaque pièce permet d'aller potentiellement vers +$w0$ ou $w1$ selon si l'un ou l'autre (ou aucun des deux) n'est +dans $\mathscr{K}$. On peut algorithmiquement faire un plan du +labyrinthe jusqu'à n'importe quelle profondeur finie. Néanmoins, si +on postule que le labyrinthe possède une sortie au bout de chaque +branche infinie (les branches finies étant des culs-de-sac), alors +aucun algorithme ne peut naviguer le labyrinthe jusqu'à une sortie, +bien que des chemins menant à une sortie existent (par le lemme de +Kőnig). +\end{corrige} \medskip @@ -703,6 +819,15 @@ l'arbre $\mathscr{K}$ ? lemme de Kőnig n'est pas démontrable en mathématiques constructives. (On ne demande pas ici un raisonnement formel précis, mais une idée.) +\begin{corrige} +Une démonstration constructive du lemme de Kőnig, formalisée dans un +système semblable à l'arithmétique de Heyting, permettrait +vraisemblablement d'extraire de la preuve un algorithme qui calcule +une branche infinie de l'arbre (cet arbre étant lui-même calculable +pour commencer). Or on vient de voir que ce n'est pas le cas, ce qui +suggère qu'une telle démonstration n'est pas possible. +\end{corrige} + % |