%% 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[1][Exercice]{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{#1~\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 / CSC-3TC34-TP\\Contrôle de connaissances — Corrigé\\{\normalsize Logique et Fondements de l'Informatique}}
\else
\title{INF110 / CSC-3TC34-TP\\Contrôle de connaissances\\{\normalsize Logique et Fondements de l'Informatique}}
\fi
\author{}
\date{29 janvier 2025}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

\textcolor{red}{À revoir.}

Les exercices et le problème 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 (tirez au moins un trait sur toute la largeur de la
feuille entre deux exercices).

Les questions du problème dépendent les unes des autres, mais ont été
rédigées de manière à ce que chacune donne toutes les informations
nécessaires pour passer à la suite.  Mais comme elles (les questions
du problème) présentent une gradation approximative de difficulté, il
est recommandé de les traiter dans l'ordre.

La longueur du sujet ne doit pas effrayer : l'énoncé du problème est
très long parce que des rappels ont été faits et que les questions ont
été rédigées de façon aussi précise que possible.  Par ailleurs, il ne
sera pas nécessaire de tout traiter pour avoir le maximum des points.

\medbreak

L'usage de tous les documents écrits (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 \emph{approximatif} et \emph{indicatif} (sur $20$) :
\textcolor{red}{à écrire}.

\ifcorrige
Ce corrigé comporte \textcolor{red}{à compléter} pages (page de garde incluse).
\else
Cet énoncé comporte \textcolor{red}{à compléter} 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


%
%
%

\bigbreak

\exercice[Problème]

\textbf{Notations :} Dans tout cet exercice, on notera comme
d'habitude $\varphi_e\colon\mathbb{N}\dasharrow\mathbb{N}$ la $e$-ième
fonction générale récursive (i.e., calculable) partielle pour
$e\in\mathbb{N}$.  On notera
\[
\mathsf{PartCalc} := \{\varphi_e \; : \; e\in\mathbb{N}\}
= \{g\colon\mathbb{N}\dasharrow\mathbb{N} \; : \;
\exists e\in\mathbb{N}.\,(g = \varphi_e)\}
\]
l'ensemble des fonctions \emph{partielles} calculables
$\mathbb{N}\dasharrow\mathbb{N}$, ainsi que
\[
\mathsf{TotIdx} := \{e\in\mathbb{N} \; : \;
\varphi_e\hbox{~est totale}\}
= \{e\in\mathbb{N} \; : \; \varphi_e\in\mathsf{TotCalc}\}
\]
l'ensemble des codes des programmes qui définissent une fonction
\emph{totale} $\mathbb{N}\to\mathbb{N}$ (i.e., terminent et renvoient
un entier quel que soit l'entier qu'on leur fournit en entrée), et
\[
\mathsf{TotCalc} := \{\varphi_e \; : \; e\in\mathsf{TotIdx}\}
= \{g\colon\mathbb{N}\to\mathbb{N} \; : \;
\exists e\in\mathbb{N}.\,(g = \varphi_e)\}
\]
l'ensemble des fonctions \emph{totales} calculables
$\mathbb{N}\to\mathbb{N}$, i.e., celles calculées par les programmes
qu'on vient de dire.

\smallskip

On va s'intéresser à la notion (qu'on va définir) de fonction
calculable $\mathsf{PartCalc} \to \mathbb{N}$ d'une part, et
$\mathsf{TotCalc} \to \mathbb{N}$ d'autre part.  (On parle parfois de
« fonctionnelles » ou de « fonction de second ordre » pour ces
fonctions sur les fonctions.)  On souligne qu'on parle bien de
fonction \emph{totales} $\mathsf{PartCalc} \to \mathbb{N}$ d'une part,
et $\mathsf{TotCalc} \to \mathbb{N}$ d'autre part.

\medskip

\textbf{Définition :} (A) Une fonction (totale !) $F\colon
\mathsf{PartCalc} \to \mathbb{N}$ est dite \emph{calculable} lorsque
la fonction $\hat F\colon \mathbb{N} \to \mathbb{N}$ définie par $\hat
F(e) = F(\varphi_e)$ est calculable.\quad (B) De même, une fonction
(totale) $F\colon \mathsf{TotCalc} \to \mathbb{N}$ est dite calculable
lorsqu'il existe une fonction $\hat F\colon \mathbb{N} \dasharrow
\mathbb{N}$ partielle calculable telle que telle que $\hat F(e) =
F(\varphi_e)$ pour tout $e \in \mathsf{TotIdx}$.

\smallskip

En français : une fonctionnelle définie sur l'ensemble des fonctions
calculables partielles ou partielles est elle-même dite calculable
lorsqu'il existe un programme qui calcule $F(g)$ à partir du code $e$
d'un programme quelconque calculant $g$.

\smallskip

{\footnotesize

Il est évident que la fonction $\hat F$ vérifie forcément
$(\varphi_{e_1} = \varphi_{e_2}) \; \Longrightarrow (\hat F(e_1) =
\hat F(e_2))$ ; c'est-à-dire qu'elle est « extensionnelle » : elle
doit renvoyer la même valeur sur deux programmes qui calculent la même
fonction (= ont la même « extension »).  D'ailleurs (on ne demande pas
de justifier ce fait, qui est facile), se donner une fonction $F\colon
\mathsf{PartCalc} \to \mathbb{N}$ revient exactement à se donner une
fonction $\hat F\colon \mathbb{N} \to \mathbb{N}$ ayant cette
propriété d'« extensionnalité » ; et de même, se donner une fonction
$F\colon \mathsf{TotCalc} \to \mathbb{N}$ revient exactement à se
donner une fonction $\hat F\colon \mathsf{TotIdx} \dasharrow
\mathbb{N}$ qui soit extensionnelle.  La définition ci-dessus dit donc
que $F$ est calculable lorsque la $\hat F$ qui lui correspond est
elle-même calculable dans le cas (A), ou la restriction à
$\mathsf{TotIdx}$ d'une fonction calculable dans le cas (B).

\par}

\medskip

\textbf{(1)} Montrer que toute fonction (totale !) calculable $F\colon
\mathsf{PartCalc} \to \mathbb{N}$ est en fait constante.

Pour cela, on pourra supposer par l'absurde que $F$ prend deux valeurs
distinctes, disons $v_1$ et $v_2$, et considérer l'ensemble des $e$
tels que $F(\varphi_e) = v_1$ (i.e., tels que $\hat F(e) = v_1$).
(Pourquoi est-il décidable ?  Et pourquoi est-ce une contradiction ?)

\medskip

\textbf{(2)} Expliquer pourquoi il existe des fonctions calculables
(totales) $F\colon \mathsf{TotCalc} \to \mathbb{N}$ qui ne sont pas
constantes.  Donner un exemple explicite.

Pour cela, on pourra penser évaluer en un point, c'est-à-dire
exécuter, le programme dont on a reçu le code en argument (on
rappellera pourquoi on peut faire cela).

\medskip

Fixons maintenant une fonction calculable $F\colon \mathsf{TotCalc}
\to \mathbb{N}$, ainsi que la fonction $\hat F\colon \mathbb{N}
\dasharrow \mathbb{N}$ qui lui correspond d'après le (B) des
définitions ci-dessus.

Dans les questions (3) à (8) qui suivent, on cherche à démontrer que
$F$ a la propriété\footnote{Si on sait ce que cela signifie, cette
propriété peut s'exprimer ainsi : $F$ est continue lorsque
$\mathsf{TotCalc}$ est muni de la topologie (héritée de la topologie)
produit sur $\mathbb{N}^{\mathbb{N}}$.} suivante (« théorème de
Kreisel-Lacombe-Shoenfield ») : quelle que soit $g \in
\mathsf{TotCalc}$, il existe $n$ telle que pour toute fonction $g' \in
\mathsf{TotCalc}$ qui coïncide avec $g$ jusqu'au rang $n$ (i.e. :
$\forall i\leq n.\,(g'(i) = g(i))$) on ait $F(g') = F(g)$.

\medskip

\textbf{Notations :} Soit $\mathsf{NulAPCR}$ l'ensemble des fonctions
$h\colon\mathbb{N}\to\mathbb{N}$ qui sont nulles à partir d'un certain
rang, c'est-à-dire telles que $\exists m. \forall i\geq m.\,(h(i) =
0)$.

\medskip

\textbf{(3)} \textbf{(a)} Expliquer pourquoi $\mathsf{NulAPCR}
\subseteq \mathsf{TotCalc}$, i.e., pourquoi toute fonction
$\mathbb{N}\to\mathbb{N}$ nulle à partir d'un certain rang est
automatiquement calculable.\quad\textbf{(b)} Montrer, plus
précisément, qu'il existe une fonction calculable $\Gamma\colon
\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ telle que toute fonction $h
\in \mathsf{NulAPCR}$ soit de la forme $\Gamma(j,\emdash)$
(c'est-à-dire $i \mapsto \Gamma(j,i)$) pour un certain $j$.
(\emph{Indication :} on pourra utiliser un codage de Gödel des suites
finies d'entiers naturels par des entiers
naturels $j$.)\quad\textbf{(c)} En déduire qu'il existe $\gamma\colon
\mathbb{N}\to\mathbb{N}$ calculable telle que toute fonction $h \in
\mathsf{NulAPCR}$ soit de la forme $\varphi_{\gamma(j)}$ pour un
certain $j$.  (\emph{Indication :} on pourra utiliser le théorème
s-m-n.)

\medskip

\textbf{Notations :} Si $g \in \mathsf{TotCalc}$ et $n\in\mathbb{N}$,
on appellera $\mathcal{B}(g,n) := \{g' \in \mathsf{TotCalc} : \forall
i\leq n.\,(g'(i) = g(i))\}$ l'ensemble des $g'$ qui coïncident avec
$g$ jusqu'au rang $n$, et $\mathcal{B}_0(g,n) := \mathcal{B}(g,n) \cap
\mathsf{NulAPCR}$ celles qui, en outre, sont nulles à partir d'un
certain rang (c'est-à-dire les fonctions prenant les valeurs
$g(0),g(1),\ldots,g(n),?,?,\ldots,?,0,0,0,\ldots$).

\medskip

\textbf{(4)} Soit $g \in \mathsf{TotCalc}$ et $n\in\mathbb{N}$.
Expliquer \emph{brièvement} pourquoi les conclusions de la
question (3) valent encore en remplaçant $\mathsf{NulAPCR}$ par
$\mathcal{B}_0(g,n)$ partout.  On notera $\gamma(g,n,j)$ la conclusion
de la dernière sous-question, c'est-à-dire que toute fonction $h \in
\mathcal{B}_0(g,n)$ soit de la forme $h = \varphi_{\gamma(g,n,j)}$
pour un certain $j$.  On expliquera \emph{brièvement} pourquoi
$\gamma(g,n,j)$ est calculable en fonction de $j$, de $n$ et du code
(dans $\mathsf{TotIdx}$) d'un programme calculant $g$.

\medskip

Si on n'a pas su traiter la question (4), pour les questions
suivantes, \textbf{on retiendra juste ceci :} $\gamma(g,n,j)$ est
calculable, et toute fonction $\mathcal{B}_0(g,n)$ est de la forme
$\varphi_{\gamma(g,n,j)}$ pour un certain $j$.

\medskip

\textbf{Algorithme A :} Pour $g \in \mathsf{TotCalc}$, on considère
maintenant le programme prenant deux entrées $d$ et $\ell$, décrit
informellement ainsi :
\begin{itemize}
\item lancer l'exécution de $\varphi_d(0)$ pour au plus $\ell$
  étapes\footnote{Si on préfère la notion d'arbre de calcul, remplacer
  par : « rechercher parmi les entiers $n\leq\ell$ un arbre de calcul
  de $\varphi_d(0)$ », et de même plus loin, remplacer « l'exécution
  s'est terminée en exactement $n\leq\ell$ étapes » par « $n$ est un
  arbre de calcul de $\varphi_d(0)$ ».  Cela ne changera rien au
  problème.} ;
\item si l'exécution ne s'est pas terminée dans le temps imparti,
  terminer en renvoyant la valeur $g(\ell)$ ;
\item sinon, disons si l'exécution s'est terminée en exactement
  $n\leq\ell$ étapes, lancer une boucle non bornée pour rechercher un
  $j \in \mathbb{N}$ tel que\footnote{On rappelle à toutes fins utiles
que $\hat F(\gamma(g,n,j)) = F(\varphi_{\gamma(g,n,j)})$ (c'est la
définition de $\hat F$).} $\hat F(\gamma(g,n,j)) \neq F(g)$ :
\begin{itemize}
\item si un tel $j$ est trouvé, on renvoie
  $\varphi_{\gamma(g,n,j)}(\ell)$,
\item sinon, bien sûr, l'algorithme ne termine pas.
\end{itemize}
\end{itemize}

\medskip

On notera $g_d(\ell)$ la valeur calculée par cet algorithme A (s'il
termine).

\medskip

\textbf{(5)} \textbf{(a)} Justifier que les opérations présentées dans
l'algorithme A ont bien un sens (i.e., que c'est bien un algorithme,
qu'on a bien défini une fonction $\mathbb{N}\times\mathbb{N}
\dasharrow \mathbb{N}$ partielle calculable $(d,\ell) \mapsto
g_d(\ell)$).\quad\textbf{(b)} En déduire qu'il existe une fonction
calculable totale $e \mapsto e_d$ telle que $g_d = \varphi_{e_d}$ pour
tout $d$.  (\emph{Indication :} on pourra utiliser le théorème s-m-n.)

\medskip

\textbf{(6)} Soit $\mathscr{H} := \{d\in\mathbb{N} :
\varphi_d(0)\downarrow\}$ l'ensemble des $d$ tels que l'exécution de
$\varphi_d(0)$ termine.\quad\textbf{(a)} Lorsque
$d\not\in\mathscr{H}$, que vaut $g_d$ ? et du coup, que vaut $\hat
F(e_d)$ ?\quad\textbf{(b)} Montrer que $\{d\in\mathbb{N} : \hat F(e_d)
= F(g)\}$ est semi-décidable.\quad\textbf{(c)} Le complémentaire
$\complement\mathscr{H} = \{d\in\mathbb{N} : \varphi_d(0)\uparrow\}$
de $\mathscr{H}$ est-il semi-décidable ?\quad\textbf{(d)} En déduire
qu'il existe $d\in\mathscr{H}$ tel que $\hat F(e_d) = F(g)$.

\medskip

\textbf{(7)} On a montré en (6) qu'il existe $d$ tel que
$\varphi_d(0)\downarrow$ et que $\hat F(e_d) = F(g)$.  Soit $n$ le
nombre d'étapes d'exécution\footnote{Ou si on préfère : l'arbre de
calcul.} de $\varphi_d(0)$.  Montrer que pour tout $g' \in
\mathcal{B}_0(g,n)$ on a $F(g') = F(g)$.  (\emph{Indication :} sinon,
la recherche d'un $j$ dans l'algorithme A aurait trouvé un $j$ et on
aurait $g_d = \varphi_{\gamma(g,n,j)}$.)

\medskip

\textbf{(8)} On a montré en (7) que pour tout $g\in\mathsf{TotCalc}$
il existe $n$ tel que pour tout $g' \in \mathcal{B}_0(g,n)$ on a
$F(g') = F(g)$.  On considère maintenant $g' \in \mathcal{B}(g,n)$
(qui n'est plus supposé nul à partir d'un certain rang) : d'après ce
qu'on vient de dire, il existe $n'$ tel que pour tout $g'' \in
\mathcal{B}_0(g',n')$ on a $F(g'') = F(g')$.  En justifiant qu'on peut
trouver $g'' \in \mathcal{B}_0(g,n) \cap \mathcal{B}_0(g',n')$,
montrer que $F(g') = F(g)$.  Conclure.

\medskip

\textbf{(9)} En observant que l'algorithme A peut s'écrire à partir du
code d'un programme calculant $g$, justifier que le $n$ dont on a
montré l'existence en (8) peut être obtenu de façon calculable en
fonction du code d'un programme calculant $g$.


%
%
%
\end{document}