%% 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\ (${\star}$)

Supposons que $A \subseteq B \subseteq \mathbb{N}$.  \textbf{(1)} Si
$B$ est décidable, peut-on conclure que $A$ est décidable ?
\textbf{(2)} Si $A$ est décidable, peut-on conclure que $B$ est
décidable ?

\begin{corrige}
La réponse est non dans les deux cas : pour le voir appelons $H := \{e
\in \mathbb{N} : \varphi_e(0)\downarrow\}$ (disons) : il est
indécidable par une des variations du problème de l'arrêt (ou par le
théorème de Rice).  Le fait que $H \subseteq \mathbb{N}$ avec
$\mathbb{N}$ décidable réfute (1), et le fait que $\varnothing
\subseteq H$ avec $\varnothing$ décidable réfute (2).
\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\ (${\star}$)

Montrer que l'ensemble des $e\in \mathbb{N}$ tels que
$\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$ (rappel : ceci signifie que
\emph{soit} $\varphi^{(1)}_e(0) \downarrow$ et $\varphi^{(1)}_e(1)
\downarrow$ et $\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$, \emph{soit}
$\varphi^{(1)}_e(0) \uparrow$ et $\varphi^{(1)}_e(1) \uparrow$) n'est
pas décidable.

\begin{corrige}
L'ensemble $F$ des fonctions partielles calculables $f\colon
\mathbb{N} \dasharrow \mathbb{N}$ telles que $f(0) = f(1)$ n'est ni
vide (la fonction totale constante de valeur $0$ est dans $F$) ni
plein (la fonction totale identité n'est pas dans $F$).  D'après le
théorème de Rice, l'ensemble des $e$ tels que $\varphi^{(1)}_e \in F$
est indécidable : c'est exactement ce qui était demandé.
\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\label{exercice-graphe-calculable}\ (${\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\label{exercice-reconnaitre-fonctions-p-r}\ (${\star}{\star}$)

Si $e \mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions
primitives récursives en une variable (= d'arité $1$) et $e \mapsto
\varphi^{(1)}_e$ celle des fonctions générales récursives en une
variable, on considère les ensembles
\[
M := \{e \in \mathbb{N} : \psi^{(1)}_e\text{~définie}\}
\]
\[
N := \{e \in \mathbb{N} : \exists
e'\in\mathbb{N}.(\psi^{(1)}_{e'}\text{~définie~et~}\varphi^{(1)}_e =
\psi^{(1)}_{e'})\}
\]
Expliquer informellement ce que signifient ces deux ensembles (en
insistant sur le rapport entre eux), dire s'il y a une inclusion de
l'un dans l'autre, et dire si l'un ou l'autre est décidable.

\begin{corrige}
L'ensemble $M$ est l'ensemble des codes valables de fonction
primitives récursives, c'est-à-dire de codes légitimes dans le langage
primitif récursif ; l'ensemble $N$ qui est $\{e \in \mathbb{N} :
\varphi^{(1)}_e \text{~est~p.r.}\}$ est l'ensemble des codes de
fonctions générales récursives qui s'avèrent être primitives
récursives (même si ce n'est pas forcément manifeste sur le
programme).  Si on préfère, $M$ est l'ensemble des \emph{intentions}
primitives récursives, alors que $N$ est l'ensemble des intentions
dont l'\emph{extension} est primitive récursive ; \textit{grosso
  modo}, l'appartenance à $M$ se lit sur le code de la fonction, celle
à $N$ se lit sur les valeurs de la fonction.

Manifestement, $M \subseteq N$, car si $\psi^{(1)}_e$ est définie, on
a $\varphi^{(1)}_e = \psi^{(1)}_e$ (la définition des fonctions
générales récursives \emph{étend} celle des fonctions p.r.).
L'inclusion dans l'autre sens ne vaut pas : on peut calculer la
fonction constante nulle en faisant une boucle infinie, ce qui fournit
un code $e$ tel que $\varphi^{(1)}_e$ est primitive récursive (donc
$e\in N$) et pourtant $\psi^{(1)}_e$ n'est pas définie (donc $e\not\in
M$).

L'ensemble $M$ est décidable : 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$ est définie), 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 très
précis, le décodage termine parce que le code d'une liste est
supérieur à tout élément de cette liste).

L'ensemble $N$ n'est pas décidable : si $F$ désigne l'ensemble des
fonctions p.r. $\mathbb{N} \to \mathbb{N}$ (c'est-à-dire l'image de
$M$ par $e \mapsto \psi^{(1)}_e$), alors $N$ est $\{e\in\mathbb{N} :
\varphi^{(1)}_e \in F\}$, et comme $F$ n'est ni vide ni l'ensemble de
toutes les fonctions générales récursives, le théorème de Rice dit
exactement que $N$ est indécidable.
\end{corrige}

%

\exercice\label{exercice-diagonalisation-0-1-fonctions-p-r}\ (${\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)}_e$ 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$ est
  définie), 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 très 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}

%

\exercice\ (${\star}{\star}{\star}$)

Soit
\[
Z := \{e \in \mathbb{N} : \exists n \in \mathbb{N}.\, (\psi^{(1)}_e(n) = 0)\}
\]
l'ensemble des codes $e$ des fonctions p.r. $\mathbb{N} \to
\mathbb{N}$ qui prennent (au moins une fois) la valeur $0$ (ici, $e
\mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions
primitives récursives en une variable).

Montrer que $Z$ est semi-décidable.  Montrer qu'il n'est pas
décidable.

\begin{corrige}
Comme dans le début du corrigé de
l'exercice \ref{exercice-diagonalisation-0-1-fonctions-p-r}, on
explique qu'on peut décider si $\psi^{(1)}_e(n)\downarrow$ (il s'agit
juste de vérifier si $e$ est un code valable de fonction p.r.) et, une
fois ce point vérifié, si $\psi^{(1)}_e(n) = 0$ (on peut calculer
$\psi^{(1)}_e(n) = \varphi^{(1)}_e(n)$ par universalité des fonctions
générales récursives).

Dès lors, pour semi-décider si $e \in Z$, il suffit de faire une
boucle infinie pour $n$ parcourant les entiers naturels, décider si
$\psi^{(1)}_e(n) = 0$ pour chacun, et si l'un d'eux est effectivement
nul, terminer et renvoyer « oui », sinon on continue la boucle.  Ceci
montre que $Z$ est semi-décidable.

Montrons qu'il n'est pas décidable : pour cela, on va ramener le
problème de l'arrêt à $Z$.  C'est en fait essentiellement ce que fait
le théorème de la forme normale de Kleene : en effet, considérons
$(p,x)$ dont il s'agit de décider si $\varphi^{(1)}_p(x)\downarrow$ :
d'après le théorème de la forme normale, ceci se produit si et
seulement si il existe un (entier codant un) arbre de calcul $n$
attestant que $\varphi^{(1)}_p(x)\downarrow$, ce qu'on écrit
$T(n,p,\dbllangle x\dblrangle)$, où $T$ est un prédicat p.r.,
c'est-à-dire qu'il s'écrit $t(n,p,\dbllangle x\dblrangle) = 0$ pour
une certaine fonction p.r. $t$ (qui teste si $n$ code un arbre de
calcul valable pour $\varphi^{(1)}_p(x)$ et renvoie $0$ si c'est le
cas, $1$ sinon).  On a ainsi $\varphi^{(1)}_p(x)\downarrow$ ssi
$\exists n\in\mathbb{N}.\, (t(n,p,\dbllangle x\dblrangle) = 0)$.
Maintenant, d'après le théorème s-m-n, on peut calculer de façon
p.r. en $p$ et $x$ le code $\rho(p,x)$ d'une fonction p.r. telle que
$\psi^{(1)}_{\rho(p,x)}(n) = t(n,p,\dbllangle x\dblrangle)$, et
d'après ce qui a été dit juste avant, on a $\rho(p,x) \in Z$,
c'est-à-dire $\exists n\in\mathbb{N}.\, (t(n,p,\dbllangle x\dblrangle)
= 0)$, se produit si et seulement si $\varphi^{(1)}_p(x)\downarrow$,
c'est-à-dire $(p,x) \in \mathscr{H}$ (où $\mathscr{H} := \{(p,x) \in
\mathbb{N}^2 : \varphi^{(1)}_p(x)\downarrow\}$ désigne le problème de
l'arrêt).  Ceci constitue une réduction \textit{many-to-one} de
$\mathscr{H}$ à $Z$, donc $Z$ ne peut pas être décidable : en effet,
si $Z$ était décidable, pour tester si $(p,x) \in \mathscr{H}$ il
suffirait de tester si $\rho(p,x) \in Z$, donc le problème de l'arrêt
serait décidable, ce qui n'est pas le cas.

(De nouveau, si on n'aime pas le théorème de la forme normale de
Kleene, on peut faire ça avec des étapes de machine de Turing :
appeler $t(n,p,x)$ la fonction qui renvoie $0$ si la machine de Turing
codée par $p$ termine en $\leq n$ étapes à partir de la configuration
initiale codée par $x$, et $1$ sinon : le reste du raisonnement est
essentiellement identique.)
\end{corrige}

%

%% \exercice\ (${\star}$)

%% Montrer qu'il existe une machine de Turing qui, quand on la lance sur
%% la configuration vierge (c'est-à-dire un ruban vierge et dans
%% l'état $1$), termine après avoir écrit son propre programme sur sa
%% bande\footnote{Par exemple avec la convention suivante : les
%% instructions du programme $\delta \colon \{1,\ldots,m\} \times \{0,1\}
%% \to \{0,\ldots,m\} \times \{0,1\} \times \{\texttt{L},\texttt{R}\}$
%% sont écrites de la gauche vers la droite dans l'ordre $\delta(1,0)$,
%% $\delta(1,1)$, $\delta(2,0)$, $\delta(2,1)$, etc., chacune étant
%% écrite sous forme du nouvel état, du nouveau symbole, et de la
%% direction codée par $\texttt{L}\mapsto 0, \texttt{R}\mapsto 1$, tous
%% les trois en unaire séparés par des $0$.}

%

\exercice\ (${\star}{\star}$)

Soit $f \colon\mathbb{N} \to \mathbb{N}$ une fonction calculable par
une machine de Turing en \emph{complexité d'espace} primitive
récursive : cela signifie qu'il existe $p \colon\mathbb{N} \to
\mathbb{N}$ primitive récursive et une machine de Turing $\mathscr{M}$
telle que si on lui présente $n \in \mathbb{N}$ en entrée (écrit avec
les conventions usuelles, c'est-à-dire en unaire sur la bande), la
machine s'arrête en temps fini en ayant écrit $f(n)$ sur la bande, et
de plus le nombre de cases de la bande que la tête de lecture a
parcourues est $\leq p(n)$ (c'est-à-dire que $\mathscr{M}$ a utilisé
$\leq p(n)$ cellules mémoire pour faire le calcul).

On veut montrer que $f$ elle-même est primitive récursive
(c'est-à-dire qu'une fonction calculable en complexité d'espace
p.r. est elle-même p.r., de la même manière qu'une fonction calculable
en complexité en temps p.r. est elle-même p.r.).

\textbf{(1)} Si $\mathscr{M}$ a $\leq m$ états, montrer que le calcul
de $f(n)$ par $\mathscr{M}$ ne peut faire intervenir qu'au plus
$m\times p(n)\times 2^{p(n)+n}$ configurations différentes (on rappelle
qu'une \emph{configuration} est la donnée d'un état, d'une position de
la tête, et de la valeur de chaque cellule du ruban).

\textbf{(2)} En déduire que le calcul de $f(n)$ par $\mathscr{M}$
termine en au plus $m\times p(n)\times 2^{p(n)+n}$ étapes
(\textit{indication :} sinon le calcul bouclerait indéfiniment, et on
a supposé que ce n'était pas le cas).

\textbf{(3)} En déduire que $f$ est primitive récursive.

\begin{corrige}
\textbf{(1)} Une configuration de l'exécution de $\mathscr{M}$ est la
donnée d'un état parmi au plus $m$, d'une position de la tête parmi au
plus $p(n)$ (puisque la tête visite au plus ce nombre de cellules), et
de la valeur de chaque cellule du ruban ; or au plus $p(n)+n$ cellules
peuvent contenir un $1$ (à n'importe quel moment de l'exécution), car
la tête n'en viiste qu'au plus $p(n)$ et au plus $n$ portent un $1$
initialement : il y a donc au plus $2^{p(n)+n}$ configurations
possibles du ruban, et au plus $m\times p(n)\times 2^{p(n)+n}$
configurations de l'ensemble de la machine.

\textbf{(2)} Si $\mathscr{M}$ retombe sur une configuration exacte
qu'elle a déjà exécutée, elle exécutera de nouveau exactement les
mêmes instructions et ne retombera indéfiniment sur cette
configuration sans jamais finir.  Comme on a supposé que le calcul
terminait, c'est qu'il doit parcourir des configurations toutes
distinctes, donc termine en au plus $m\times p(n)\times 2^{p(n)+n}$
étapes.

\textbf{(3)} On vient de montrer que le calcul de $f$ par
$\mathscr{M}$ es fait en temps au plus $m\times p(n)\times
2^{p(n)+n}$.  Mais ceci est une fonction p.r. de $n$ (car $p$ l'est,
et que $k \mapsto 2^k$ l'est, et que $m$ est une constante ici).  Donc
$f$ est calculée en complexité en temps p.r., donc elle est elle-même
p.r.
\end{corrige}



%
%
%
\end{document}