First version of test for 2024-01-26.

1 files changed, 625 insertions, 0 deletions

diff --git a/controle-20240126.tex b/controle-20240126.tex
new file mode 100644
index 0000000..52c4e3e
--- /dev/null
+++ b/controle-20240126.tex
@@ -0,0 +1,625 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,hmargin=2cm,vmargin=3cm]{geometry}
+\usepackage[french]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+\usepackage{mathpartir}
+\usepackage{flagderiv}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows}
+\usepackage{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\medskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\newcommand{\dbllangle}{\mathopen{\langle\!\langle}}
+\newcommand{\dblrangle}{\mathclose{\rangle\!\rangle}}
+\newcommand{\dottedlimp}{\mathbin{\dot\Rightarrow}}
+\newcommand{\dottedland}{\mathbin{\dot\land}}
+\newcommand{\dottedlor}{\mathbin{\dot\lor}}
+\newcommand{\dottedtop}{\mathord{\dot\top}}
+\newcommand{\dottedbot}{\mathord{\dot\bot}}
+\newcommand{\dottedneg}{\mathop{\dot\neg}}
+\mathchardef\emdash="07C\relax
+%
+\DeclareUnicodeCharacter{00A0}{~}
+%
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF110\\Contrôle de connaissances — Corrigé\\{\normalsize Logique et Fondements de l'Informatique}}
+\else
+\title{INF110\\Contrôle de connaissances\\{\normalsize Logique et Fondements de l'Informatique}}
+\fi
+\author{}
+\date{26 janvier 2024}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants.  Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+\medbreak
+
+L'usage de tous les documents (notes de cours manuscrites ou
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 3h
+
+Barème \textcolor{red}{à remplir}.
+
+\ifcorrige
+Ce corrigé comporte \textcolor{red}{à remplir} pages (page de garde incluse).
+\else
+Cet énoncé comporte \textcolor{red}{à remplir} pages (page de garde incluse).
+\fi
+
+\vfill
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+\textbf{Motivations :} On s'intéresse dans cet exercice à la notion de
+\emph{réel calculable}, qu'on va définir comme une formalisation
+possible d'un nombre réel exact pouvant être manipulé par un
+ordinateur.  L'idée la plus évidente pour définir les réels
+calculables est sans doute de considérer ceux dont une écriture
+binaire est une fonction calculable (et de les représenter par le code
+d'un programme qui calcule cette fonction) : on va voir plus loin que
+cette définition « naïve » souffre de graves problèmes.  À la place,
+on va définir un réel calculable comme un réel dont on peut calculer
+par un programme une approximation rationnelle à $\varepsilon$ près
+pour n'importe quel $\varepsilon>0$ donné en entrée (et représenter le
+réel par le code d'un programme qui prend $\varepsilon$ et renvoie
+l'approximation).  Pour rendre cette définition plus commode à manier,
+on va se limiter à $\varepsilon$ de la forme $\frac{1}{2^n}$ et
+renvoyer une approximation elle-même de la forme $\frac{k}{2^n}$ (cela
+ne change rien d'essentiel).
+
+\smallskip
+
+On fait donc les définitions suivantes :
+\begin{itemize}
+\item Un \textbf{dyadique} est un rationnel de la forme
+  $\frac{k}{2^n}$ avec $k\in\mathbb{Z}$ et $n\in \mathbb{N}$ (i.e.,
+  son dénominateur est une puissance de $2$).  Pour être plus précis,
+  on peut appeler \textbf{dyadique de niveau $n$} un rationnel de la
+  forme $\frac{k}{2^n}$ avec $k\in\mathbb{Z}$ (pour ce $n$-là ; noter
+  qu'on ne demande pas que $\frac{k}{2^n}$ soit irréductible, par
+  exemple $42 = \frac{84}{2} = \frac{168}{2^2} = \cdots$ est un
+  dyadique de tout niveau).
+\item Si $x \in \mathbb{R}$, un \textbf{numérateur d'approximation
+  dyadique de niveau $n$} de $x$ est un entier $k$ tel que $|k-2^n\,
+  x|\leq 1$.  L'approximation dyadique elle-même est alors par
+  définition $\frac{k}{2^n}$, et vérifie donc $|\frac{k}{2^n}-x|\leq
+  \frac{1}{2^n}$.
+\item Un réel $x \in \mathbb{R}$ est dit \textbf{calculable} lorsqu'il
+  existe une fonction \emph{calculable} $\mathbb{N} \to \mathbb{Z}, n
+  \mapsto k_n$ telle que $k_n$ soit un numérateur d'approximation
+  dyadique de niveau $n$ de $x$.  Autrement dit, il existe un
+  programme qui, prenant $n$ en entrée, renvoie une approximation
+  dyadique $\frac{k}{2^n}$ de niveau $n$ de $x$ (représentée sous
+  forme du numérateur de la fraction, puisque le dénominateur est par
+  définition $2^n$).  Une telle fonction $n \mapsto k_n$, ou un
+  programme qui la calcule, est dit \textbf{représenter} le réel $x$.
+\end{itemize}
+
+\smallskip
+
+À titre d'exemple, l'entier $42$ est un réel calculable puisque la
+fonction $n \mapsto 42\times 2^n$ est évidemment calculable.
+
+\smallskip
+
+On prendra garde aux faits suivants :
+\begin{itemize}
+\item Un même réel $x$ a plusieurs approximations dyadiques de
+  niveau $n$ (il en a même toujours $2$ ou $3$, puisque leurs
+  numérateurs sont les entiers contenus dans l'intervalle $[2^n\,
+    x-1\,;\,2^n\, x + 1]$ de longueur $2$).  À titre d'exemple, le
+  réel $0$ peut être représenté par n'importe quelle fonction
+  calculable $n \mapsto k_n$ renvoyant un $k_n$ dans $\{-1,0,1\}$.
+\item Même une fois fixée la fonction calculable $n \mapsto k_n$
+  représentant un réel calculable $x$, il y a (toujours) plusieurs
+  programmes qui la calculent (« intentions »).
+\end{itemize}
+
+\smallskip
+
+On ne demande pas de justifier le fait évident qu'un programme
+informatique peut manipuler des données dans $\mathbb{Z}$ (entiers
+relatifs arbitraires), notamment faire de l'arithmétique basique
+dessus (sommes, différences, produits, exponentiation, division
+euclidienne, etc.).
+
+Lorsqu'il est demandé d'écrire un programme, on l'écrira dans un
+langage de programmation raisonnable quelconque (capable de manipuler
+des entiers arbitrairement grands), ou sous forme de pseudocode.  Par
+exemple, s'il est demandé d'écrire un programme représentant l'entier
+$42$ on pourra écrire « \texttt{lambda n: 42 * 2**n} » ou
+« \texttt{fun n -> 42 * (pow 2 n)} » ou n'importe quoi d'aisément
+compréhensible de la sorte, mais en précisant ce qui n'est pas évident
+(par exemple que « \texttt{pow} » est une fonction calculant
+l'exponentiation entière).  On pourra aussi librement décider si ce
+langage manipule des fonctions calculables sous forme de codes de
+Gödel de programmes les calculant, ou sous forme de fonctions
+informatiques (langage fonctionnel), ou même mélanger les deux au
+besoin (à condition de le préciser).
+
+\smallskip
+
+\centerline{*}
+
+\smallskip
+
+\textbf{(1)} Expliquer pourquoi, donnés $p\in\mathbb{Z}$ et
+$q\in\mathbb{N}\setminus\{0\}$ et $n\in\mathbb{N}$, on peut calculer
+algorithmiquement un numérateur d'approximation dyadique de niveau $n$
+de $\frac{p}{q}$.  En déduire que tout rationnel est un réel
+calculable, et, plus précisément, écrire un programme qui, donnés
+$p$ et $q$, renvoie une fonction représentant le rationnel
+$\frac{p}{q}$ comme réel calculable.
+
+\begin{corrige}
+Si $\lfloor z\rfloor$ désigne la partie entière de $z$, la fonction
+$(p,q,n) \mapsto \lfloor 2^n\, \frac{p}{q}\rfloor$ est calculable car
+c'est la partie quotient de la division euclidienne de $2^n\, p$
+par $q$, et il s'agit d'un numérateur d'approximation dyadique de
+niveau $n$ de $\frac{p}{q}$ puisque $|\lfloor z\rfloor - z| \leq 1$.
+Donc, la fonction qui à $p$ et $q$ associe le code d'une fonction
+calculant $n \mapsto \lfloor 2^n\, \frac{p}{q}\rfloor$ est calculable
+(par le théorème s-m-n si on veut être très précis).  Un tel programme
+s'écrit par exemple « \texttt{fun p -> fun q -> fun n -> (p * (pow 2
+  n)) / q} » en supposant que « \texttt{pow} » représente
+l'exponentiation entière et ‘\texttt{/}’ la division euclidienne.
+\end{corrige}
+
+\smallskip
+
+\textbf{(2)} Montrer que si $x$ est un réel calculable alors $-x$ est
+calculable, et, plus précisément, écrire un programme qui, donné une
+fonction qui représente $x$, en renvoie une qui représente $-x$.
+Faire de même pour $|x|$ (on rappelle à toutes fins utiles que
+$\big||u|-|v|\big| \leq |u-v|$).
+
+\begin{corrige}
+Si $k$ est un numérateur d'approximation dyadique de niveau $n$ de $x
+\in \mathbb{R}$, c'est-à-dire $|k - 2^n\,x| \leq 1$, alors $|(-k) -
+2^n\,(-x)| \leq 1$ (car $|-z| = |z|$).  Ceci montre que si $n \mapsto
+k_n$ représente $x$ alors $n \mapsto -k_n$ représente $-x$, et elle
+est certainement calculable si la première l'est.  Un programme
+calculant une fonction représentant $-x$ à partir d'une fonction
+représentant $x$ s'écrit par exemple « \texttt{fun xf -> fun n -> -(xf
+  n)} ».
+
+Pour la valeur absolue, on procède de même en remarquant que si $|k -
+2^n\,x| \leq 1$, alors $|(|k|) - 2^n\,(|x|)| \leq 1$ (d'après
+l'inégalité qui a été rappelée).  Ceci montre que si $n \mapsto k_n$
+représente $x$ alors $n \mapsto |k_n|$ représente $|x|$ : un programme
+correspondant s'écrit par exemple « \texttt{fun xf -> fun n -> abs(xf
+  n)} ».
+\end{corrige}
+
+\smallskip
+
+\textbf{(3)} Expliquer pourquoi, si $k$ est un numérateur
+d'approximation dyadique de niveau $n+r$ de $x \in \mathbb{R}$ (avec
+$n,r\in\mathbb{N}$), alors $k$ est aussi un numérateur d'approximation
+dyadique de niveau $n$ de $2^r x$.  En déduire que si $x$ est un réel
+calculable et $r\in\mathbb{N}$ alors $2^r x$ est calculable, et, plus
+précisément, écrire un programme qui, donnés $r$ et une fonction qui
+représente $x$, renvoie une fonction qui représente $2^r x$.
+
+\begin{corrige}
+Dire que $k$ est un numérateur d'approximation dyadique de
+niveau $n+r$ de $x$ signifie par définition $|k - 2^{n+r}\,x| \leq 1$.
+C'est exactement dire que $|k - 2^n\,(2^r\,x)| \leq 1$, c'est-à-dire
+que $k$ est aussi un numérateur d'approximation dyadique de niveau $n$
+de $2^r x$.  On en déduit que si $n \mapsto k_n$ représente $x$ alors
+$n \mapsto k_{n+r}$ représente $2^r x$.  Un programme calculant une
+fonction représentant $2^r x$ à partir de $r$ et d'une fonction
+représentant $x$ s'écrit par exemple « \texttt{fun r -> fun xf -> fun
+  n -> xf (n+r)} ».
+\end{corrige}
+
+\smallskip
+
+\textbf{(4)} Expliquer comment, donné $\ell \in \mathbb{Z}$, on peut
+trouver algorithmiquement un entier $k \in \mathbb{Z}$ tel que
+$[\frac{\ell}{4}-\frac{1}{2}\,;\,\frac{\ell}{4}+\frac{1}{2}]
+\subseteq[k-1\,;\,k+1]$ (on pourra faire un dessin de ces
+intervalles).  En tirer une façon de trouver algorithmiquement un
+numérateur d'approximation dyadique de niveau $n$ de $x+y$ à partir de
+numérateurs d'approximations dyadiques de niveau $n+2$ de $x$ et $y$
+respectivement.
+
+En déduire que si $x$ et $y$ sont calculables alors $x+y$
+est calculable, et, plus précisément, et, plus précisément, écrire un
+programme qui, donnés des fonctions qui représentent $x$ et $y$, en
+renvoie une qui représente $x+y$.
+
+\begin{corrige}
+Dire $[\frac{\ell}{4}-\frac{1}{2}\,;\,\frac{\ell}{4}+\frac{1}{2}]
+\subseteq[k-1\,;\,k+1]$ équivaut à $[\ell-2\,;\,\ell+2]
+\subseteq[4k-4\,;\,4k+4]$, c'est-à-dire $4k-4 \leq \ell-2$ et $\ell+2
+\leq 4k+4$, soit encore $\ell-2 \leq 4k \leq \ell+2$, autrement dit,
+on cherche un multiple de $4$ compris au sens large entre les entiers
+$\ell-2$ et $\ell+2$, ce qui existe certainement car il y a $5$
+entiers consécutifs dans cet intervalle : pour faire ça
+algorithmiquement, on peut appeler $k =
+\lfloor\frac{\ell+2}{4}\rfloor$ la partie quotient de la division
+euclidienne de $\ell+2$ par $4$, on aura alors $4k+r = \ell+2$ avec
+reste $0\leq r<4$, donc $\ell-2 < 4k \leq \ell+2$.
+
+Si $i,j$ désignent des numérateurs d'approximations dyadiques de
+niveau $n+2$ de $x$ et $y$ respectivement, c'est-à-dire $|i -
+2^{n+2}\,x| \leq 1$ et $|j - 2^{n+2}\,y| \leq 1$, on a alors $|(i+j) -
+2^{n+2}\,(x+y)| \leq 2$ par inégalité triangulaire, c'est-à-dire, en
+posant $\ell := i+j$, que $|\frac{\ell}{4} - 2^n\,(x+y)| \leq
+\frac{1}{2}$.  Or on vient de voir comment en tirer algorithmiquement
+un $k$ tel que
+$[\frac{\ell}{4}-\frac{1}{2}\,;\,\frac{\ell}{4}+\frac{1}{2}]
+\subseteq[k-1\,;\,k+1]$, c'est-à-dire exactement que $|\frac{\ell}{4}
+- 2^n\,(x+y)| \leq \frac{1}{2}$ implique $|k - 2^n\,(x+y)| \leq 1$,
+c'est-à-dire que $k$ est un numérateur d'approximation dyadique de
+niveau $n$ de $x+y$.
+
+On en déduit que si $n \mapsto i_n$ représente $x$ et que $n \mapsto
+j_n$ représente $y$ alors $n \mapsto \lfloor(i_{n+2} + j_{n+2} +
+2)/4\rfloor$ représente $x+y$.  Un programme calculant une fonction
+représentant $x+y$ à partir de fonctions représentant $x$ et $y$
+s'écrit par exemple « \texttt{fun xf -> fun yf -> fun n -> ((xf (n+2)) +
+  (yf (n+2)) + 2)/4} ».
+\end{corrige}
+
+\smallskip
+
+\textbf{(5)} Montrer qu'un réel calculable $z$ représenté par une
+fonction $n \mapsto k_n$ vérifie $z\leq 0$ si et seulement on a $k_n
+\leq 1$ pour tout $n$.  En déduire comment, donnée une fonction $n
+\mapsto k_n$ représentant $z$ calculable, et en \emph{supposant}
+$z>0$, on peut calculer algorithmiquement un $n\in\mathbb{N}$ tel que
+$z \geq \frac{1}{2^n}$.
+
+De façon analogue, montrer que, donné une fonction $n \mapsto k_n$
+représentant $z$ calculable, et en supposant seulement $z\neq 0$, on
+peut décider algorithmiquement si $z<0$ ou $z>0$.
+
+\begin{corrige}
+Si $k_n \leq 1$ pour tout $n$, alors $z \leq \frac{k_n+1}{2^n} \leq
+\frac{1}{2^{n-1}}$ pour tout $n$, donc $z \leq 0$.  Réciproquement, si
+$z \leq 0$, alors $0 \geq \frac{k_n-1}{2^n}$ donc $k_n \leq 1$ pour
+tout $n$.
+
+On en déduit que si on \emph{suppose} $z>0$, il existe un indice $n$
+tel que $k_n \geq 2$ dans toute fonction représentant $z$ ; et on a
+alors $z \geq \frac{k_n-1}{2^n} \geq \frac{1}{2^n}$ comme recherché.
+Pour trouver ce $n$, il suffit d'effectuer une boucle infinie
+calculant $k_n$ en s'arrêtant dès que $k_n \geq 2$ : d'après ce qui
+vient d'être dit, l'hypothèse $z>0$ garantit la terminaison de la
+boucle.
+
+Si maintenant on suppose simplement $z\neq 0$, il existe soit un
+indice $n$ tel que $k_n \geq 2$ soit un indice tel que $k_n \leq -2$ :
+pour décider le signe de $z$, il suffit d'effectuer une boucle infinie
+jusqu'à ce qu'une de ces conditions soit satisfaite, et de renvoier
+« positif » ou « négatif » selon qu'on a trouvé un $n$ vérifiant l'un
+ou l'autre.
+\end{corrige}
+
+\smallskip
+
+\textbf{(6)} Indépendamment de toutes les questions qui précèdent,
+montrer qu'il n'existe pas de programme qui, donné le code d'un autre
+programme $e$, décide si ce dernier représente un réel (nécessairement
+calculable).  Autrement dit, la fonction qui à $e$ associe $1$ si $e$
+calcule une fonction $n \mapsto k_n$ représentant un certain réel $x$,
+et $0$ sinon, n'est pas calculable.
+
+\begin{corrige}
+C'est une conséquence du théorème de Rice : l'ensemble des fonctions
+partielles $\mathbb{N} \dasharrow \mathbb{Z}$ représentant un réel
+n'est ni vide ni plein (il n'est pas vide car la fonction constante
+$0$ est dedans, et pas plein parce que la fonction définie nulle part
+n'est pas dedans), donc le théorème de Rice affirme que l'ensemble des
+$e$ tels que $\varphi_e$ soit dans cet ensemble n'est pas décidable.
+\end{corrige}
+
+\smallskip
+
+\textbf{(7)} Soit $e$ un programme (vu comme l'indice d'une fonction
+générale récursive $\varphi_e$).  Soit $\eta(e)$ le réel défini de la
+manière suivante :
+\[
+\eta(e) =
+\left\{
+\begin{array}{ll}
+\displaystyle\frac{1}{2^m}&\text{~si le calcul de $\varphi_e(0)$ termine en $m$ étapes (et pas moins)}\\
+\vphantom{\displaystyle\frac{0}{0}}0&\text{~si $\varphi_e(0){\uparrow}$}\\
+\end{array}
+\right.
+\]
+(Plus exactement, il faudrait plutôt écrire « $\eta(e) =
+\frac{1}{2^m}$ si $m$ est le code d'un arbre de calcul pour
+$\varphi_e(0)$ » à la première ligne.)  Expliquer comment, donnés $e$
+et $n \in \mathbb{N}$, calculer algorithmiquement un numérateur
+d'approximation dyadique de niveau $n$ de $\eta(e)$.
+
+En déduire qu'on peut écrire un programme qui, donné $e$, renvoie une
+fonction représentant le réel $\eta(e)$ (en tant réel calculable).
+
+\begin{corrige}
+On a vu en cours qu'il est possible de tester algorithmiquement si le
+calcul de $\varphi_e(0)$ termine en $m$ étapes (ou, si on préfère, si
+$n$ est un arbre de calcul pour $\varphi_e(0)$).  Pour calculer un
+numérateur d'approximation dyadique de niveau $n$ de $\eta(e)$, on va
+faire ce test : on lance l'exécution de $\varphi_e(0)$ sur $n$
+étapes : si le calcul termine au bout de en $m\leq n$ étapes (ou, si
+on préfèr, si on trouve un arbre de calcul $m\leq n$), on renvoie
+l'approximant $\frac{1}{2^m}$, c'est-à-dire qu'on renvoie le
+numérateur $2^{n-m}$, qui convient car $\eta(e) = \frac{1}{2^m}$
+exactement ; s'il ne termine pas dans le temps imparti, on renvoie le
+numérateur $0$, qui convient car $\eta(e) \leq \frac{1}{2^n}$.
+\end{corrige}
+
+\smallskip
+
+\textbf{(8)} Expliquer l'erreur dans la réponse suivante à la
+question (7) : « On lance le calcul de $\varphi_e(0)$ : s'il termine
+en (exactement) $m$ étapes, on renvoie (une fonction représentant)
+$\frac{1}{2^m}$, qui est calculable d'après la question (1), sinon on
+renvoie la fonction constamment nulle. » On expliquera aussi en quoi
+on n'a pas commis cette erreur en répondant à ladite question.
+
+\begin{corrige}
+L'erreur est dans le mot « sinon » : si on lance le calcul de
+$\varphi_e(0)$, on ne peut pas savoir à l'avance s'il va terminer : on
+peut certes renvoyer $\frac{1}{2^m}$ s'il termine en exactement $m$
+étapes, mais si on fait ça il n'y a pas de « sinon » possible, car on
+est parti dans une boule infinie.  Et il n'y a pas de moyen de savoir
+\textit{a priori} si la boucle terminera, car le problème de l'arrêt
+est indécidable (même pour $\varphi_e(0)$).
+
+On n'a pas commis cette erreur, car on a pris \emph{d'abord} $n$, qui
+agit comme borne sur le nombre d'étapes d'exécution : on renvoie une
+approximation dyadique de niveau $n$ de $\eta(e)$, qui peut être $0$
+si le calcul de $\varphi_e(0)$ n'a pas terminé dans le temps imparti.
+\end{corrige}
+
+\smallskip
+
+\textbf{(9)} Déduire de la question (8) qu'il n'y a pas d'algorithme
+qui, donnée une fonction représentant un réel calculable $x$, teste si
+$x\neq 0$ ou $x=0$ (i.e., renvoie « vrai » si $x\neq 0$ et « faux » si
+$x=0$).
+
+\begin{corrige}
+Si un tel algorithme existait, appliqué à $\eta(e)$ (ou plus
+exactement, à une fonction représentant $\eta(e)$, dont on a vu à la
+question (8) qu'elle se déduit algorithmiquement de $e$), il
+permettrait de tester si $\varphi_e(0){\downarrow}$.  Or on a vu que
+ceci n'est pas faisable algorithmiquement.  C'est donc que
+l'algorithme évoqué n'existe pas.
+\end{corrige}
+
+\smallskip
+
+Pour la question suivante, on \emph{admettra} le résultat suivant
+(plus ou moins vu en TD) : il n'existe pas d'algorithme qui, donné le
+code d'un programme $e$, termine toujours en temps fini et renvoie
+« vrai » si $\varphi_e(0){\downarrow} = 0$ et « faux » si
+$\varphi_e(0){\downarrow} \neq 0$ (si $\varphi_e(0){\uparrow}$ il
+aurait le droit de répondre n'importe quoi mais avec l'obligation de
+terminer).
+
+\smallskip
+
+\textbf{(10)} En modifiant un peu la construction proposée en (7) (on
+définira $\eta'(e)$ valant $\frac{1}{2^m}$ ou $-\frac{1}{2^m}$ ou $0$
+selon des cas judicieusement choisis), montrer qu'il n'est même pas
+possible algorithmiquement de tester si un réel calculable est $\geq
+0$ ou $\leq 0$, i.e., il n'existe pas d'algorithme qui, donnée une
+fonction représentant un réel calculable $x$, peut renvoyer « vrai »
+si $x\geq 0$ ou « faux » si $x\leq 0$ (les deux réponses étant
+acceptées si $x=0$).
+
+\begin{corrige}
+On définit
+\[
+\eta'(e) =
+\left\{
+\begin{array}{ll}
+\displaystyle\frac{1}{2^m}&\text{~si le calcul de $\varphi_e(0)$ termine en $m$ étapes (et pas moins) et $\varphi_e(0) = 0$}\\
+\displaystyle-\frac{1}{2^m}&\text{~si le calcul de $\varphi_e(0)$ termine en $m$ étapes (et pas moins) et $\varphi_e(0) \neq 0$}\\
+\vphantom{\displaystyle\frac{0}{0}}0&\text{~si $\varphi_e(0){\uparrow}$}\\
+\end{array}
+\right.
+\]
+
+Le même argument qu'à la question (7) montre que $\eta'(e)$ est
+calculable à partir de $e$ : donné un niveau $n$, il suffit de lancer
+l'exécution de $\varphi_e(0)$ sur $n$ étapes et, si elle termine en
+$m\leq n$ étapes, renvoyer l'approximant $\frac{1}{2^m}$ ou
+$-\frac{1}{2^m}$ (c'est-à-dire le numérateur $2^{n-m}$ ou $-2^{n-m}$)
+selon que le résultat qu'on a calculé est $0$ ou $\neq 0$, et
+sinon $0$.  Comme en (9), décider si $\eta'(e)\leq 0$ ou $\eta'(e)\geq
+0$ (en acceptant n'importe quelle réponse si c'est $0$) reviendrait à
+décider si $\varphi_e(0){\downarrow} = 0$ ou $\varphi_e(0){\downarrow}
+\neq 0$ (en acceptant n'importe quelle réponse si
+$\varphi_e(0){\uparrow}$, mais toujours avec l'obligation de
+terminer), et on a indiqué que ce n'était pas possible.
+\end{corrige}
+
+\smallskip
+
+Si $x$ est un réel entre $0$ et $1$ (pour simplifier), on rappelle
+qu'une \textbf{écriture binaire} de $x$ est une suite $(u_n)_{n\geq
+  1}$ à valeurs dans $\{0,1\}$ telle que $x = \sum_{n=1}^{+\infty}
+u_n\cdot 2^{-n}$.  Une telle suite existe toujours (par exemple, on
+peut prendre celle donnée $u_n = \lfloor 2^n x\rfloor - 2\lfloor
+2^{n-1} x\rfloor$ où $\lfloor \emdash \rfloor$ désigne la partie
+entière), mais elle n'est pas unique en général (par exemple
+$\frac{1}{2}$ admet les deux écritures binaires $0.100000\ldots$ et
+$0.011111\ldots$ ; en fait, ce sont exactement les dyadiques qui
+admettent plus d'une écriture binaire, et ils en admettent exactement
+deux).
+
+On dira qu'un réel entre $0$ et $1$ est \textbf{naïvement calculable}
+lorsqu'il admet une écriture binaire $n \mapsto u_n$ calculable.
+
+\smallskip
+
+\textbf{(11)} Montrer qu'un réel (entre $0$ et $1$) naïvement
+calculable est calculable, et plus précisément qu'il existe un
+algorithme qui, donnée une fonction qui calcule l'écriture binaire de
+$x$, renvoie sa représentation comme réel calculable (comme définie au
+début de ce problème).
+
+\begin{corrige}
+Si $x = \sum_{i=1}^{+\infty} u_i\cdot 2^{-i}$, alors $2^n\,x =
+\sum_{i=1}^{+\infty} u_i\cdot 2^{n-i}$ donc en appelant $k_n =
+\sum_{i=1}^{n} u_i\cdot 2^{n-i}$ (il s'agit d'un entier), on voit que
+$2^n\,x - k_n = \sum_{i=1}^{+\infty} u_{n+i}\cdot 2^{-i}$ est compris
+entre $0$ et $1$, et notamment $k_n$ est un numérateur d'approximation
+dyadique de niveau $n$ de $x$.  Ceci fournit un algorithme calculant
+$n \mapsto k_n$ à partir de $n \mapsto u_n$.
+\end{corrige}
+
+\smallskip
+
+\textbf{(12)} En utilisant la question (10), montrer qu'il n'existe
+pas d'algorithme qui, donnée une fonction $n \mapsto k_n$ représentant
+un réel $x$ calculable entre $0$ et $1$, renvoie une fonction
+calculable $n \mapsto u_n$ qui soit une écriture binaire de $x$.
+
+\begin{corrige}
+Si un tel algorithme existait, on pourrait l'appliquer à $x_e =
+\frac{1}{2}(\eta'(e)+1)$, où $\eta'(e)$ est le réel calculable en
+fonction de $e$ défini à la question (10) dont on ne peut pas
+algorithmiquement en fonction de $e$ décider s'il est $\leq 0$ ou
+$\geq 0$.  Or le premier chiffre de l'écriture binaire de $x_e$ va
+être $0$ ou $1$ selon que $x_e \leq \frac{1}{2}$ ou $x_e \geq
+\frac{1}{2}$ (avec les deux possibilités si $x_e = \frac{1}{2}$),
+c'est-à-dire selon que $\eta'(e)\leq 0$ ou $\eta'(e)\geq 0$ : on ne
+peut donc pas algorithmiquement calculer ce chiffre en fonction
+de $e$.
+\end{corrige}
+
+\smallskip
+
+\textbf{(13)} En utilisant de nouveau la question (10), montrer qu'il
+n'existe pas d'algorithme qui, donnés deux réels calculables naïfs
+$x,y$ (avec $x$ entre $\frac{1}{2}$ et $1$ et $y$ entre $0$ et
+$\frac{1}{2}$ pour simplifier) sous forme d'une fonction calculant une
+écriture binaire, renvoie $x-y$ sous cette même forme.
+
+\begin{corrige}
+Considérons $\eta'(e)$ le réel calculable en fonction de $e$ défini à
+la question (10).  On peut l'écrire sous la forme $\eta'_+(e) -
+\eta'_-(e)$ avec $\eta'_+(e) = \frac{1}{2}(\eta'(e) + |\eta'(e)|)$ et
+$\eta'_-(e) = \frac{1}{2}(-\eta'(e) + |\eta'(e)|)$, tous deux positifs
+et tous deux valant soit $0$ soit $\frac{1}{2^m}$ pour un certain $m$.
+Les questions (2) et (4) montrent qu'on peut calculer $\eta'_+(e)$ et
+$\eta'_-(e)$, au sens des réels calculables, en fonction de $e$.  De
+plus, sachant que chacun vaut soit $0$ soit $\frac{1}{2^m}$ pour un
+certain $m$ (ou bien en regardant directement la construction de
+$\eta'(e)$), il est aussi facile d'en produire une écriture binaire :
+pour calculer le $n$-ième chiffre de son écriture binaire, si tous les
+précédents étaient $0$, on demande une approximation dyadique de
+niveau $n+2$ et on renvoie $0$ si elle est dans $\{-1,0,1\}$, sinon on
+renvoie $1$ et ensuite uniquement des $0$.  Les réels $x_e =
+\frac{1}{2}(\eta'_+(e) + 1)$ et $y_e = \frac{1}{2}\eta'_-(e)$ sont
+donc tels qu'on peut calculer une écriture binaire en fonction de $e$,
+pourtant on ne peut pas en calculer pour $x_e - y_e$ comme on l'a
+expliqué à la question précédente.
+\end{corrige}
+
+\smallskip
+
+\textbf{(14)} Montrer que, la question (12) nonobstant, tout réel
+calculable (entre $0$ et $1$) est naïvement calculable.  (On pourra
+distinguer deux cas : soit le réel est dyadique, soit il ne l'est
+pas.)  On expliquera pourquoi ce n'est pas une contradiction qu'on ait
+montré que les réels calculables et naïvement calculables coïncident,
+mais qu'on peut algorithmiquement soustraire les réels calculables
+mais pas les réels naïvement calculables.
+
+\begin{corrige}
+Tout réel dyadique est évidemment calculable.  Il reste à montrer que
+si $x$ est un réel entre $0$ et $1$ calculable et qui n'est pas
+dyadique, alors il est naïvement calculable.  Pour cela, on applique
+l'algorithme suivant : pour calculer le $n$-ième chiffre $u_n$ de
+l'écriture binaire de $x$, on calcule une fonction représentant $2^n x
+- 1$, lequel est $\neq 0$ d'après l'hypothèse que $x$ n'est pas
+dyadique, donc d'après la question (5) on peut décider s'il est $<0$
+ou $>0$, et $u_n$ vaut $0$ ou $1$ dans ces deux cas respectifs.  Tout
+ceci est calculable.
+
+Les réels calculables et naïvement calculables sont donc les mêmes en
+tant qu'ensembles, mais leur représentation informatiques diffèrent :
+on peut passer algorithmiquement de la représentation naïve par
+l'écriture binaire à la représentation par approximations, mais en
+général pas dans l'autre sens (la difficulté étant que tant qu'on est
+très proche d'un dyadique on ne sait jamais si on doit émettre le
+chiffre $0$ ou $1$ dans l'écriture binaire).
+\end{corrige}
+
+
+%
+%
+%
+\end{document}