Some exercises on computability.

1 files changed, 350 insertions, 0 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
new file mode 100644
index 0000000..26840c0
--- /dev/null
+++ b/exercices-inf110.tex
@@ -0,0 +1,350 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\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{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}[section]
+\newcommand\thingy{%
+\refstepcounter{comcnt}\medskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
+%
+\newcommand{\dbllangle}{\mathopen{\langle\!\langle}}
+\newcommand{\dblrangle}{\mathclose{\rangle\!\rangle}}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+%
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\footnotesize\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\relax\else\egroup\fi\par}
+%
+%
+%
+\begin{document}
+\title{Logique et Fondements de l'Informatique\\Exercices}
+\author{David A. Madore}
+\maketitle
+
+\centerline{\textbf{INF1110}}
+
+\vskip2cm
+
+{\footnotesize
+\immediate\write18{sh ./vc > vcline.tex}
+\begin{center}
+Git: \input{vcline.tex}
+\\
+(Recopier la ligne ci-dessus dans tout commentaire sur ce document)
+\end{center}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pretolerance=8000
+\tolerance=50000
+
+
+%
+%
+%
+
+\section{Calculabilité}
+
+
+\exercice\ ($\star$)
+
+On considère la fonction $f\colon \mathbb{N} \to \mathbb{N}$ qui à $n
+\in \mathbb{N}$ associe le $n$-ième chiffre de l'écriture décimale de
+$\sqrt{2} \approx 1.41421356237309504880\ldots$, c'est-à-dire $f(0) =
+1$, $f(1) = 4$, $f(2) = 1$, $f(3) = 4$, etc.
+
+La fonction $f$ est-elle calculable ?  Est-elle primitive récursive ?
+On expliquera précisément pourquoi.
+
+\begin{corrige}
+On peut calculer $f(n)$ selon l'algorithme suivant : calculer $N =
+10^n$, puis pour $i$ allant de $0$ à $2N$, tester si $i^2 \leq 2 N^2 <
+(i+1)^2$ : lorsque c'est le cas (et ce sera le cas pour exactement un
+$i$ dans l'intervalle), renvoyer le reste $i\% 10$ de la division
+euclidienne de $i$ par $10$.
+
+Cet algorithme est correct car l'inégalité $i^2 \leq 2 N^2 < (i+1)^2$
+testé équivaut à $\frac{i}{N} \leq \sqrt{2} < \frac{i+1}{N}$, ce qui
+se produit pour exactement un $i$, à savoir $\lfloor \sqrt{2}\times
+10^n \rfloor$ (on peut arrêter la boucle à $2N$ car $\sqrt{2} < 2$),
+et que le dernier chiffre décimal $i\% 10$ de ce $i$ est le $n$-ième
+chiffre de l'écriture décimale de $\sqrt{2}$.
+
+D'autre part, comme on a donné un algorithme explicite, $f$ est
+calculable.  Mieux : comme la boucle utilisée est bornée \textit{a
+  priori}, $f$ est primitive récursive.
+\end{corrige}
+
+%
+
+\exercice\label{exercice-image-calculable-est-semi-decidable}\ ($\star$)
+
+\textbf{(1)} Soit $f\colon \mathbb{N} \to \mathbb{N}$ totale
+calculable.  Montrer que l'image $f(\mathbb{N})$ (c'est-à-dire $\{f(i)
+: i\in\mathbb{N}\}$) est semi-décidable.
+
+\textbf{(2)} Soit $f\colon \mathbb{N} \to \mathbb{N}$ totale
+calculable et strictement croissante.  Montrer que l'image
+$f(\mathbb{N})$ (c'est-à-dire $\{f(i) : i\in\mathbb{N}\}$) est
+décidable.
+
+\begin{corrige}
+\textbf{(1)} L'algorithme évident suivant semi-décide $\{f(i) :
+i\in\mathbb{N}\}$ : donné $m \in \mathbb{N}$ l'entier à tester, faire
+une boucle infinie sur $i$ parcourant les entiers naturels et pour
+chacun, tester si $f(i) = m$ : si c'est le cas, terminer et répondre
+« oui », sinon, continuer la boucle.
+
+\textbf{(2)} L'algorithme évident suivant décide $\{f(i) :
+i\in\mathbb{N}\}$ : donné $m \in \mathbb{N}$ l'entier à tester, faire
+une boucle pour $i$ parcourant les entiers naturels, et pour chacun,
+tester si $f(i) = m$ : si c'est le cas, terminer et répondre « oui »,
+tandis que si $f(i) > m$, terminer et répondre « non », sinon,
+continuer la boucle.  La boucle termine en temps fini car $f(i) \geq
+i$ (inégalité claire pour une fonction $\mathbb{N} \to \mathbb{N}$
+strictement croissante) et notamment la boucle s'arrêtera au pire
+lorsque $i$ vaut $m+1$.  (Du coup, si on préfère, on peut réécrire la
+boucle potentiellement infinie comme une boucle pour $i$ allant de $0$
+à $m$.)
+\end{corrige}
+
+%
+
+\exercice\label{exercice-image-fonction-partielle-calculable}\ ($\star\star$)
+
+\textbf{(1)} Soit $B \subseteq \mathbb{N}$ semi-décidable et non-vide.
+Montrer qu'il existe $f\colon \mathbb{N} \to \mathbb{N}$ totale
+calculable telle que $f(\mathbb{N}) = B$.
+
+(\emph{Indication :} si $m_0 \in B$ et si $B$ est semi-décidé par le
+$e$-ième programme, i.e., $B = \{m : \varphi_e(m)\downarrow\}$, on
+définira $\tilde f\colon \mathbb{N}^2 \to \mathbb{N}$ par $\tilde
+f(n,m) = m$ si $T(n,e,\dbllangle m\dblrangle)$, où $T(n,e,v)$ est
+comme dans le théorème de la forme normale de Kleene\footnote{Rappel :
+  c'est-à-dire que $T(n,e,\dbllangle \underline{x}\dblrangle)$
+  signifie : « $n$ est le code d'un arbre de calcul de
+  $\varphi_e(\underline{x})$ termine » (le résultat
+  $\varphi_e(\underline{x})$ du calcul étant alors noté $U(n)$).}, et
+$\tilde f(n,m) = m_0$ sinon.  Alternativement, si on préfère raisonner
+sur les machines de Turing : si $B$ est semi-décidé par la machine de
+Turing $\mathscr{M}$, on définit $\tilde f(n,m) = m$ si $\mathscr{M}$
+termine sur l'entrée $m$ en $\leq n$ étapes d'exécution, et $\tilde
+f(n,m) = m_0$ sinon.)
+
+\textbf{(2)} Soit $f\colon \mathbb{N} \dasharrow \mathbb{N}$ partielle
+calculable.  Montrer que l'image $f(\mathbb{N})$ (c'est-à-dire $\{f(i)
+: i\in\mathbb{N} \text{~et~} f(i){\downarrow}\}$) est semi-décidable.
+(\emph{Indication :} chercher à formaliser l'idée de lancer les
+calculs des différents $f(i)$ « en parallèle ».)
+
+\begin{corrige}
+\textbf{(1)} La fonction $\tilde f \colon \mathbb{N}^2 \to \mathbb{N}$
+définie dans l'indication est calculable (et d'ailleurs même primitive
+récursive) : si on a pris la définition avec $T$ le fait que $T$ soit
+p.r. fait partie du théorème de la forme normale ; si on préfère les
+machines de Turing, c'est le fait qu'on peut simuler l'exécution de
+$\mathscr{M}$ pour $n$ étapes (de façon p.r.).  Et on voit qu'on a
+$\tilde f(n,m) \in B$ dans tous les cas : donc $\tilde f(\mathbb{N}^2)
+\subseteq B$.  Mais réciproquement, si $m \in B$, alors
+$\varphi_e(m)\downarrow$ (si on préfère les machines de Turing,
+$\mathscr{M}$ termine sur l'entrée $m$), et ceci dit précisément qu'il
+existe $n$ tel que $\tilde f(n,m) = m$, donc $m \in \tilde
+f(\mathbb{N}^2)$ ; bref, $B \subseteq \tilde f(\mathbb{N}^2)$.  On a
+donc $\tilde f(\mathbb{N}^2) = B$ par double inclusion.  Quitte à
+remplacer $\tilde f \colon \mathbb{N}^2 \to \mathbb{N}, (n,m) \mapsto
+\tilde f(n,m)$ par $f \colon \mathbb{N} \to \mathbb{N}, \langle
+n,m\rangle \mapsto \tilde f(n,m)$, on a $f(\mathbb{N}) = B$.
+
+\textbf{(2)} Ici on ne peut pas appliquer bêtement l'algorithme exposé
+dans l'exercice \ref{exercice-image-calculable-est-semi-decidable}
+question (1) car si le calcul de $f(i)$ ne termine pas, il bloquera
+tous les suivants.  Il faut donc mener le calcul des $f(i)$ « en
+parallèle ».  On va procéder par énumération des couples $(n,i)$ et
+lancer le calcul de $f(i)$ sur $n$ étapes.
+
+Plus précisément : considérons l'algorithme suivant : il prend en
+entrée un entier $m$ dont il s'agit de semi-décider s'il appartient à
+$f(\mathbb{N})$.  L'algorithme fait une boucle infinie sur $p$
+parcourant les entiers naturels : chaque $p$ est d'abord décodé comme
+le code $\langle n,i\rangle$ d'un couple d'entiers naturels (ceci est
+bien sûr calculable).  On teste si l'exécution de $f(i)$ termine en
+$\leq n$ étapes (ou, si on préfère le théorème de la forme de normale,
+on teste si $T(n,e,\dbllangle i\dblrangle)$, où $e$ est un code de la
+fonction $f = \varphi^{(1)}_e$) : si oui, et si la valeur $f(i)$
+calculée est égale à l'entier $m$ considéré, on termine en renvoyant
+« oui », sinon on continue la boucle.
+
+Cet algorithme semi-décide bien $f(\mathbb{N})$ : en effet, dire que
+$m \in f(\mathbb{N})$, équivaut à l'existence de $i$ tel que
+$f(i){\downarrow} = m$, c'est-à-dire à l'existence de $n,i$ tel que
+l'algorithme renverra « oui » en testant $\langle n,i\rangle$.
+
+(\emph{Variante :} plutôt qu'utiliser le codage des couples $\langle
+n,i\rangle$, on peut aussi faire ainsi : on parcourt les entiers
+naturels $p$ en une boucle infini et pour chacun on effectue deux
+boucles bornées pour $0\leq n\leq p$ et $0\leq i\leq p$ : peu
+importent les bornes précises, l'important est que pour $p$ assez
+grand on va finir par tester le couple $(n,i)$.)
+\end{corrige}
+
+%
+
+\exercice\ ($\star\star$)
+
+Soit $f\colon \mathbb{N} \to \mathbb{N}$ une fonction totale : montrer
+qu'il y a équivalence entre les affirmations suivantes :
+\begin{enumerate}
+\item la fonction $f$ est calculable,
+\item le graphe $\Gamma_f := \{(i,f(i)) : i\in\mathbb{N}\} =
+  \{(i,q)\in\mathbb{N}^2 : q=f(i)\}$ de $f$ est décidable,
+\item le graphe $\Gamma_f$ de $f$ est semi-décidable.
+\end{enumerate}
+
+(Montrer que (3) implique (1) est le plus difficile : on pourra
+commencer par s'entraîner en montrant que (2) implique (1).  Pour
+montrer que (3) implique (1), on pourra chercher une façon de tester
+en parallèle un nombre croissant de valeurs de $q$ de manière à
+s'arrêter si l'une quelconque convient.  On peut s'inspirer de
+l'exercice \ref{exercice-image-fonction-partielle-calculable}
+question (2).)
+
+\begin{corrige}
+Montrons que (1) implique (2) : si on dispose d'un algorithme
+$\mathscr{F}$ capable de calculer $f(i)$ en fonction de $i$, alors il
+est facile d'écrire un algorithme $\mathscr{D}$ capable de décider si
+$q=f(i)$ (il suffit de calculer $f(i)$ avec l'algorithme $\mathscr{F}$
+supposé exister, de comparer avec la valeur de $q$ fournie, et de
+renvoyer vrai/$1$ si elles sont égales, et faux/$0$ sinon),
+c'est-à-dire que l'algorithme $\mathscr{D}$ décide $\Gamma_f$.
+
+Le fait que (2) implique (3) est évident car tout ensemble décidable
+est en particulier semi-décidable.
+
+Montrons que (2) implique (1) même si ce ne sera au final pas utile :
+supposons qu'on ait un algorithme $\mathscr{D}$ qui décide $\Gamma_f$
+(i.e., donnés $(i,q)$, termine toujours en temps fini, en répondant
+« oui » si $q=f(i)$ et « non » si $q\neq f(i)$), et on cherche à
+écrire un algorithme $\mathscr{F}$ qui calcule $f(i)$.  Pour cela,
+donné un $i$, il suffit de lancer l'algorithme $\mathscr{D}$
+successivement sur les valeurs $(i,0)$ puis $(i,1)$ puis $(i,2)$ et
+ainsi de suite (c'est-à-dire faire une boucle infinie sur $q$
+parcourant les entiers naturels et lancer $\mathscr{D}$ sur chaque
+couple $(i,q)$) jusqu'à trouver un $q$ pour lequel $\mathscr{D}$
+réponde vrai : on termine alors en renvoyant la valeur $q$ qu'on a
+trouvée, qui vérifie $q=f(i)$ par définition de $\mathscr{D}$.
+L'algorithme $\mathscr{F}$ qu'on vient de décrire termine toujours car
+$f$ était supposée totale, donc il existe bien un $q$ pour lequel
+$\mathscr{D}$ répondra « oui ».
+
+Reste à montrer que (3) implique (1) : supposons maintenant qu'on ait
+un algorithme $\mathscr{S}$ qui « semi-décide » $\Gamma_f$ (i.e.,
+donnés $(i,q)$, termine en temps fini et répond « oui » si $q=f(i)$,
+et ne termine pas sinon), et on cherche à écrire un algorithme qui,
+donné $i$ en entrée, calcule $f(i)$.  Notre algorithme
+(appelons-le $\mathscr{F}$) fait une boucle infinie sur $p$ parcourant
+les entiers naturels : chaque $p$ est d'abord décodé comme le code
+$\langle n,q\rangle$ d'un couple d'entiers naturels.  On teste si
+l'exécution de $\mathscr{S}$ sur l'entrée $(i,q)$ termine en $\leq n$
+étapes (ce qui est bien faisable algorithmiquement) : si oui, on
+renvoie la valeur $q$ ; sinon, on continue la boucle.
+
+Cet algorithme $\mathscr{F}$ termine toujours : en effet, pour chaque
+$i$ donné, il existe $q$ tel que $(i,q) \in \Gamma_f$, à savoir $q =
+f(i)$ ; et alors l'algorithme $\mathscr{S}$ doit terminer sur l'entrée
+$(i,q)$, c'est-à-dire que pour $n$ assez grand, il termine en $\leq n$
+étapes, donc $\mathscr{F}$ terminera lorsqu'il arrivera à $p = \langle
+n,q\rangle$, et il renverra bien $q$ comme annoncé.  On a donc montré
+que $f$ était calculable puisqu'on a exhibé un algorithme qui la
+calcule.
+
+(Comme dans
+l'exercice \ref{exercice-image-fonction-partielle-calculable}, on peut
+utiliser le $T$ de la forme normale de Kleene au lieu de parler
+d'« étapes » d'exécution d'une machine de Turing.  Aussi, plutôt
+qu'utiliser le codage des couples $\langle n,i\rangle$, on peut
+préférer faire ainsi : on parcourt les entiers naturels $p$ en une
+boucle infini et pour chacun on effectue deux boucles bornées pour
+$0\leq n\leq p$ et $0\leq q\leq p$ : peu importent les bornes
+précises, l'important est que pour $p$ assez grand on va finir par
+tester le couple $(n,q)$.)
+\end{corrige}
+
+%
+
+\exercice\ ($\star\star\star$)
+
+On considère la fonction $f\colon \mathbb{N}^2 \to \mathbb{N}$ qui à
+$(e,x)$ associe $1$ si $\psi^{(1)}_e(x) = 0$ et $0$ sinon (y compris
+si $\psi^{(1)}_e$ n'est pas définie), où $e \mapsto \psi^{(1)}$ est la
+numérotation standard des fonctions primitives récursives en une
+variable (= d'arité $1$).
+
+La fonction $f$ est-elle calculable ?  Est-elle primitive récursive ?
+On expliquera précisément pourquoi.  (On s'inspirera de résultats vus
+en cours.)  Cela changerait-il si on inversait les valeurs $0$ et $1$
+dans $f$ ?
+
+\begin{corrige}
+La fonction $f$ est calculable.  En effet,
+\begin{itemize}
+\item on peut décider de façon algorithmique si $e$ est un numéro
+  valable de fonction primitive récursive (i.e., si $\psi^{(1)}_e$),
+  il s'agit pour cela simplement de « décoder » $e$ et de vérifier
+  qu'il suit les conventions utilisées pour numéroter les fonctions
+  primitives récursives (pour être bien précis, le décodage termine
+  parce que le code d'une liste est supérieur à tout élément de cette
+  liste) ;
+\item lorsque c'est le cas, on peut calculer $\psi^{(1)}_e(x)$ car
+  quand elle est définie elle coïncide avec $\varphi^{(1)}_e(x)$
+  (numérotation des fonctions générales récursives), dont on sait
+  qu'il est calculable (universalité) ;
+\item calculer $f$ ne pose ensuite aucune difficulté.
+\end{itemize}
+
+Montrons que $f$ n'est pas primitive récursive (on a vu en cours que
+$(e,x) \mapsto \psi^{(1)}_e(x)$ ne l'est pas, mais cela ne suffit
+pas : on pourrait imaginer que le fait qu'il soit égal à $0$ soit plus
+facile à tester).  Pour cela, supposons par l'absurde que $f$ soit
+primitive récursive.  Par le théorème de récursion de Kleene, il
+existe $e$ tel que $\psi^{(1)}_e(x) = f(e,x)$.  Or la définition même
+de $f$ fait que $f(e,x) \neq \psi^{(1)}_e(x)$ dans tous les cas : ceci
+est une contradiction.  Donc $f$ n'est pas primitive récursive.
+
+Cela ne change bien sûr rien d'échanger $0$ et $1$, c'est-à-dire de
+remplacer $f$ par $1 - f$ (l'une est récursive, resp. p.r., ssi
+l'autre l'est), mais la démonstration ne se serait pas appliquée telle
+quelle.
+\end{corrige}
+
+
+
+
+%
+%
+%
+\end{document}