%% 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}