From 2a0d406b122f0160ffa8452a393c672bcc7373e3 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 20 Jan 2026 20:20:20 +0100
Subject: Write answer key for the exercise on the Kleene tree.

---
 controle-20260126.tex | 157 +++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 141 insertions(+), 16 deletions(-)

(limited to 'controle-20260126.tex')

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}
+
 
 
 %
-- 
cgit v1.2.3