Add an exercise on the Kleene tree.

1 files changed, 166 insertions, 0 deletions

diff --git a/controle-20260126.tex b/controle-20260126.tex
index 1b22f2a..109b334 100644
--- a/controle-20260126.tex
+++ b/controle-20260126.tex
@@ -130,6 +130,8 @@ Git: \input{vcline.tex}
 
 \pagebreak
 
+\iftrue
+
 
 %
 %
@@ -538,6 +540,170 @@ Qed.
 \end{corrige}
 
 
+\fi
+
+
+%
+%
+%
+
+\exercice
+
+\textbf{Rappels de quelques définitions habituelles.}  On rappelle
+qu'un \textbf{mot binaire [fini]} est une suite finie (éventuellement
+vide, c'est-à-dire de longueur nulle) de $0$ et de $1$.  On notera
+$\{0,1\}^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}$ (ici,
+$\varepsilon$ désigne le mot vide) l'ensemble de tous les mots
+binaires.  La \textbf{longueur} $|w|$ d'un mot binaire $w \in
+\{0,1\}^*$ est le nombre total de bits qu'il contient (p.ex., $|00|=2$
+et $|\varepsilon|=0$), et nous suivrons la convention de numéroter les
+bits de la gauche vers la droite de $0$ à $|w|-1$ (par exemple, le bit
+numéroté $0$ de $1010$ vaut $1$, tandis que son bit numéroté $3$
+vaut $0$).  On dit qu'un mot binaire $u$ est un \textbf{préfixe} d'un
+mot binaire $v$ lorsque $v$ commence par les bits de $u$, ou,
+formellement : $|u|\leq|v|$ et pour chaque $0\leq j < |u|$, le bit
+numéroté $j$ de $v$ est égal au bit numéroté $j$ de $u$.  (Par
+exemple, $1010$ est un préfixe de $1010111$, tout mot binaire est un
+préfixe de lui-même, et $\varepsilon$ est un préfixe de n'importe quel
+mot binaire.)
+
+\medskip
+
+On pourra utiliser sans justification et sans commentaire le fait que
+les mots binaires peuvent être manipulés algorithmiquement (via un
+codage de Gödel qu'on ne demande pas de préciser) : notamment,
+calculer la longueur d'un mot, ou renvoyer son bit numéroté $i$, sont
+des opération calculables.
+
+\medskip
+
+On appelle \textbf{arbre de Kleene} l'ensemble $\mathscr{K} \subseteq
+\{0,1\}^*$ de mots binaires défini de la manière suivante : un mot
+binaire $w \in \{0,1\}^*$ de longueur $|w|$ appartient à $\mathscr{K}$
+lorsque, pour chaque $0 \leq i < |w|$, le bit numéroté $i$ de $w$ vaut
+\begin{itemize}
+\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$,
+\item et arbitraire sinon
+\end{itemize}
+où $\varphi_i$ désigne la $i$-ième fonction générale récursive.
+\emph{Si on préfère} parler en termes de machines de Turing, on pourra
+changer la définition en :
+\begin{itemize}
+\item $0$ si la $i$-ième machine de Turing
+  termine\footnote{Sous-entendu : à partir d'une bande vierge (ou
+  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$,
+\item et arbitraire sinon
+\end{itemize}
+(cela ne changera rien de substantiel aux raisonnements).
+Informellement dit, l'appartenance d'un mot $w$ à $\mathscr{K}$ est
+déterminée par le résultat de l'exécution des $|w|$ premiers
+programmes, chacun jusqu'à la borne $|w|$, et le bit numéroté $i$
+de $w$ est contraint, si le programme $i$ termine, par le résultat de
+celui-ci.
+
+(On prendra note du fait que $\varepsilon \in \mathscr{K}$ car la
+contrainte « pour chaque $0\leq i < |w|$ » est vide — donc
+trivialement vérifiée — vu que $|\varepsilon|=0$.)
+
+\bigskip
+
+\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}$.
+
+\medskip
+
+On dit que $\mathscr{K}$ est un \textbf{arbre} de mots
+binaires\footnote{Si cette terminologie semble mystérieuse,
+l'explication est que le graphe (infini d'après la question (3)) dont
+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).
+
+\medskip
+
+\textbf{(2)} Montrer que $\mathscr{K}$ est une partie \emph{décidable}
+(i.e., calculable) de $\{0,1\}^*$.
+
+\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.
+
+\medskip
+
+On appelle \textbf{branche infinie} de $\mathscr{K}$ une suite infinie
+$(b_i)_{i\in\mathbb{N}}$ de bits (i.e., un élément de
+$\{0,1\}^{\mathbb{N}}$) dont tous les préfixes appartiennent
+à $\mathscr{K}$, c'est-à-dire : $b_0\cdots b_{\ell-1} \in \mathscr{K}$
+pour tout $\ell \in \mathbb{N}$.
+
+\medskip
+
+\textbf{(4)} \emph{Indépendamment de tout ce qui précède,} montrer
+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.
+\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
+$e$ d'une machine de Turing, \emph{termine toujours en temps fini}, et
+renvoie
+\begin{itemize}
+\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$,
+\item et une valeur arbitraire sinon.
+\end{itemize}
+
+\emph{Indication :} utiliser l'astuce de Quine pour construire un
+programme qui fait le contraire de ce qu'on lui prédit.
+
+\emph{Attention !} On demande dans cette question une démonstration
+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 ».
+
+\medskip
+
+\textbf{(5)} Déduire de (4) qu'il n'existe aucune branche infinie
+calculable de $\mathscr{K}$.
+
+\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.
+
+\medskip
+
+\textbf{(6)} Que peut-on conclure du lemme de Kőnig concernant
+l'arbre $\mathscr{K}$ ?
+
+\medskip
+
+\textbf{(7)} Expliquer pourquoi la question (5) \emph{suggère} que le
+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.)
+
+
 
 %
 %