%% 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{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} \ifcorrige \title{Logique et Fondements de l'Informatique\\Exercices corrigés} \else \title{Logique et Fondements de l'Informatique\\Exercices} \fi \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}{\star}$)\par\nobreak 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}$)\par\nobreak 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{exercise-computable-image-is-semidecidable}\ (${\star}{\star}$)\par\nobreak \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}$)\par\nobreak 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{exercise-image-computable-partial-function}\ (${\star}{\star}{\star}$)\par\nobreak \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{exercise-computable-image-is-semidecidable} 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{exercise-indices-total-functions}\ (${\star}{\star}{\star}$)\par\nobreak Soit \[ T := \{e \in \mathbb{N} : \varphi^{(1)}_e\text{~est~totale}\} \] l'ensemble des codes des fonctions générales récursives totales (c'est-à-dire telles que $\forall n\in\mathbb{N}.\,(\varphi^{(1)}_e(n)\downarrow)$). On se propose de montrer que ni $T$ ni son complémentaire $\complement T$ ne sont semi-décidables. \textbf{(1)} Montrer en guise d'échauffement que $T$ n'est pas décidable. \textbf{(2)} Soit $H := \{d \in \mathbb{N} : \varphi^{(1)}_d(0)\downarrow\}$ (variante du problème de l'arrêt). Rappeler brièvement pourquoi $H$ est semi-décidable mais non décidable, et pourquoi son complémentaire $\complement H$ n'est pas semi-décidable. \textbf{(3)} Montrer qu'il existe une fonction $\rho \colon \mathbb{N} \to \mathbb{N}$ (totale) calculable (d'ailleurs même p.r.) telle que $\varphi^{(1)}_d(0)\downarrow$ si et seulement si $\varphi^{(1)}_{\rho(d)}$ est totale (\emph{indication :} on pourra par exemple construire un programme $e$ qui ignore son argument et qui simule $d$ sur l'entrée $0$). Reformuler cette affirmation comme une réduction. En déduire que le complémentaire $\complement T$ de $T$ n'est pas semi-décidable. \textbf{(4)} Montrer qu'il existe une fonction $\sigma \colon \mathbb{N} \to \mathbb{N}$ (totale) calculable (d'ailleurs même p.r.) telle que $\varphi^{(1)}_d(0)\downarrow$ si et seulement si $\varphi^{(1)}_{\sigma(d)}$ \emph{n'est pas} totale (\emph{indication :} on pourra par exemple construire un programme $e$ qui lance $d$ sur l'entrée $0$ pour un nombre d'étapes donné en argument, et fait une boucle infinie si cette exécution termine avant le temps imparti). Reformuler cette affirmation comme une réduction. En déduire que $T$ n'est pas semi-décidable. \begin{corrige} On notera « $\varphi$ » pour « $\varphi^{(1)}$ » de manière à alléger les notations. \textbf{(1)} L'ensemble des fonctions calculables $\mathbb{N} \dasharrow \mathbb{N}$ qui sont en fait totales ($\mathbb{N} \to \mathbb{N}$) n'est ni vide (la fonction totale constante de valeur $0$ est dedans) ni plein (la fonction nulle part définie n'est pas dedans). D'après le théorème de Rice, l'ensemble $T$ des $e$ tels que $\varphi_e$ soit totale est indécidable : c'est exactement ce qui était demandé. \textbf{(2)} Toujours d'après le théorème de Rice, ou comme variante du problème de l'arrêt (qui s'y ramène par le théorème s-m-n), l'ensemble $H$ n'est pas décidable. Il est cependant semi-décidable par universalité (on peut lancer l'exécution de $e$ sur l'entrée $0$ et, si elle termine, renvoyer « oui »). On en déduit que $\complement H$ n'est pas semi-décidable (car si $H$ et $\complement H$ étaient semi-décidables, $H$ serait décidable, ce qu'il n'est pas). \textbf{(3)} Considérons la fonction $\rho$ qui prend en entrée un programme $d$ (supposé d'un argument) et renvoie le programme $e =: \rho(d)$ (toujours d'un argument) qui ignore son argument et exécute $d$ sur l'entrée $0$ : essentiellement par le théorème s-m-n, cette fonction $\rho$ est totale calculable (d'ailleurs même p.r.). Par définition, on a $\varphi_{\rho(d)}(n) = \varphi_d(0)$ (rappelons que ceci signifie que chacun est défini ssi l'autre l'est et, le cas échéant, que ces valeurs sont égales). Notamment, si $\varphi_d(0)\downarrow$, alors $\varphi_{\rho(d)}$ est totale (et constante !), tandis que si $\varphi_d(0)\uparrow$, alors $\varphi_{\rho(d)}$ n'est nulle part définie (donc certainement pas totale). Bref, on a construit $\rho\colon\mathbb{N}\to\mathbb{N}$ totale calculable telle que $d \in H$ si et seulement si $\rho(d) \in T$, ou, ce qui revient au même, $d \in \complement H$ si et seulement si $\rho(d) \in \complement T$. En termes de réductions, ceci signifie $H \mathrel{\leq_\mathrm{m}} T$, ou, ce qui revient au même, $\complement H \mathrel{\leq_\mathrm{m}} \complement T$ (le symbole « $\mathrel{\leq_\mathrm{m}}$ » désignant la réduction many-to-one). Comme $\complement H$ n'est pas semi-décidable, $\complement T$ ne l'est pas non plus. \emph{Remarque :} On n'est pas obligé d'utiliser le terme de « réduction many-to-one » pour argumenter que $\complement T$ n'est pas semi-décidable : on peut simplement dire « supposant par l'absurde que $\complement T$ soit semi-décidable, on pourrait semi-décider $\complement H$ de la façon suivante : donné $d$, on calcule $\rho(d)$, on semi-décide si $\rho(d) \in \complement T$ et, si c'est le cas, on termine en renvoyant “oui” ; or ce n'est pas possible, d'où une contradiction ». \textbf{(4)} Considérons la fonction $\sigma$ qui prend en entrée un programme $d$ (supposé d'un argument) et renvoie le programme $e := \sigma(d)$ (toujours d'un argument) défini ainsi : le programme $e$ prend en entrée un nombre $n$ et exécute le programme $d$ sur l'entrée $0$ pendant $\leq n$ étapes (mettons que ce soient des machines de Turing, sinon remplacer cet argument par une recherche d'arbre de calcul parmi les entiers naturels de $0$ à $n$) : si cette exécution a terminé en $\leq n$ étapes, alors $d$ effectue une boucle infinie, sinon $d$ termine (et renvoie, disons, $1729$). Il n'y a pas de difficulté à coder ce programme $e$ (on rappelle qu'exécuter un programme donné sur $\leq n$ étapes est calculable, d'ailleurs même primitif récursif), et de plus la fonction $\sigma$ transformant $d$ en $e$ est elle-même calculable (et d'ailleurs elle aussi primitive récursive). Par définition de $e := \sigma(d)$, la fonction $\varphi_e$ est : \begin{itemize} \item soit définie pour tout $n$ (et de valeur $1729$), ce qui se produit exatement lorsque l'exécution de $d$ ne termine jamais, i.e. $\varphi_d(0) \uparrow$, \item soit définie jusqu'en un certain $n$ et non définie après, ce qui se produit exactement lorsque l'exécution de $d$ termine en un certain nombre d'étapes, i.e. $\varphi_d(0) \downarrow$. \end{itemize} En particulier, si $\varphi_d(0)\uparrow$, alors $\varphi_{\sigma(d)}$ est totale (et constante !), tandis que si $\varphi_d(0)\downarrow$, alors $\varphi_{\sigma(d)}$ n'est pas totale. Bref, on a construit $\sigma\colon\mathbb{N}\to\mathbb{N}$ totale calculable telle que $d \in H$ si et seulement si $\sigma(d) \not\in T$, ou, ce qui revient au même, $d \in \complement H$ si et seulement si $\sigma(d) \in T$. En termes de réductions, ceci signifie $\complement H \mathrel{\leq_\mathrm{m}} T$. Comme $\complement H$ n'est pas semi-décidable, $T$ ne l'est pas non plus. \emph{Remarque :} Comme dans la question précédente, on n'est pas obligé d'utiliser le terme de « réduction many-to-one » pour argumenter que $T$ n'est pas semi-décidable : on peut simplement dire « supposant par l'absurde que $T$ soit semi-décidable, on pourrait semi-décider $\complement H$ de la façon suivante : donné $d$, on calcule $\sigma(d)$, on semi-décide si $\sigma(d) \in T$ et, si c'est le cas, on termine en renvoyant “oui” ; or ce n'est pas possible, d'où une contradiction ». \end{corrige} % \exercice\label{exercise-computable-graph}\ (${\star}{\star}{\star}$)\par\nobreak 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{exercise-image-computable-partial-function} 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{exercise-image-computable-partial-function}, 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{exercise-recognizing-p-r-functions}\ (${\star}{\star}{\star}$)\par\nobreak 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 une fonction non p.r., jeter le résultat, et renvoyer $0$, 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{exercise-diagonalization-0-1-p-r-functions}\ (${\star}{\star}{\star}{\star}$)\par\nobreak 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) ; ici, $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}{\star}$)\par\nobreak 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{exercise-diagonalization-0-1-p-r-functions}, 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}{\star}$)\par\nobreak %% 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}{\star}$)\par\nobreak On rappelle que le mot « configuration », dans le contexte de l'exécution d'une machine de Turing, désigne la donnée de l'état interne de la machine, de la position de la tête de lecture, et de la totalité de la bande. (Et la « configuration vierge » est la configuration où l'état est $1$, la tête est à la position $0$, et la bande est entièrement remplie de $0$.) On considère l'ensemble $\mathscr{F}$ des machines de Turing $M$ dont l'exécution, à partir de la configuration vierge $C_0$, conduit à un nombre fini de configurations distinctes (i.e., si on appelle $C^{(n)}$ la configuration atteinte au bout de $n$ étapes d'exécution en démarrant sur $C_0$, on demande que l'ensemble $\{C^{(n)} : n\in \mathbb{N}\}$ soit fini). \textbf{(1)} Montrer que $\mathscr{F}$ est semi-décidable. (\emph{Indication :} on pourra commencer par remarquer, en le justifiant, que « passer par un nombre fini de configurations distinctes » équivaut à « terminer ou revenir à une configuration déjà atteinte ».) \textbf{(2)} Montrer que $\mathscr{F}$ n'est pas décidable. (\emph{Indication :} si on savait décider $\mathscr{F}$ on saurait décider le problème de l'arrêt.) \begin{corrige} \textbf{(1)} Commençons par remarquer que « passer par un nombre fini de configurations distinctes » équivaut à « terminer ou revenir à une configuration déjà atteinte ». En effet, dans un sens, si l'exécution termine (i.e., termine en temps fini), il est évident qu'elle n'a parcouru qu'un nombre fini de configurations distinctes ; mais si elle revient à une configuration déjà atteinte, la machine boucle indéfiniment à partir de cet état puisque l'exécution est déterministe (la configuration contient toute l'information nécessaire à l'exécution de la machine $M$) : si $C^{(i)} = C^{(j)}$ avec $i i_k$) on insère un nouveau couple : comme l'encodage et le décodage des couples (et notamment l'insertion d'un élément dans une liste) sont primitifs récursifs, tout ceci est primitif récursif. \textbf{(2)} Le tableau est codé sous forme d'entier naturel comme on l'a dit, donc il devient une simple variable de boucle, sur laquelle on peut effectuer des lectures et modifications par les fonctions qu'on a expliquées (et qui sont primitives récursives). Le fait de disposer d'une variable dans une boucle (bornée !) pour un algorithme primitif récursif est bien permis (essentiellement par la récursion primitive, qui permet précisément la modification d'une variable à chaque tour de boucle). \end{corrige} % \exercice\ (${\star}{\star}{\star}{\star}{\star}$)\par\nobreak On rappelle la définition de la fonction d'Ackermann $A\colon \mathbb{N}^3 \to \mathbb{N}$ : \[ \begin{aligned} A(m,n,0) &= m+n \\ A(m,0,1) &= 0 \\ A(m,0,k) &= 1\text{~si~}k\geq 2 \\ A(m,n+1,k+1) &= A(m,\,A(m,n,k+1),\,k) \end{aligned} \] On a vu en cours que cette fonction est calculable mais non primitive récursive. On admettra sans discussion que $A(m,n,k)$ est croissante en chaque variable dès que $m\geq 2$ et $n\geq 2$. On pourra aussi utiliser sans discussion les faits suivants : \[ \begin{aligned} A(m,n,1) &= mn \\ A(m,n,2) &= m^n \\ A(0,n,k) &= ((n+1)\%2)\text{~si~}k\geq 3 \\ A(1,n,k) &= 1\text{~si~}k\geq 2 \\ A(m,1,k) &= m\text{~si~}k\geq 1 \\ A(2,2,k) &= 4 \\ \end{aligned} \] On considérera aussi la \emph{fonction indicatrice du graphe} de $A$, c'est-à-dire la fonction $B\colon \mathbb{N}^4 \to \mathbb{N}$ : \[ \begin{array}{ll} B(m,n,k,v) = 1 &\text{~si~}v = A(m,n,k) \\ B(m,n,k,v) = 0 &\text{~sinon} \\ \end{array} \] \textbf{(1)} Écrire un algorithme qui calcule $A(m,n,k)$ à partir de $m$, $n$, $k$ et d'un \emph{majorant} $b$ de $A(m,n,k)$ selon le principe suivant : si $m\geq 2$ et $n\geq 2$, pour chaque $\ell$ allant de $0$ à $k$ et chaque $i$ allant de $0$ à $b$ (bien noter : c'est $b$ et pas $n$ ici), on calcule $A(m,i,\ell)$, et on la stocke dans la case $(i,\ell)$ d'un tableau, à condition que les valeurs déjà calculées et contenues dans le tableau permettent de la calculer (pour les petites valeurs $m\leq 1$ ou $n\leq 1$ on utilise les formules données ci-dessus ; sinon, on essaye d'utiliser la formule de récurrence en consultant le tableau). Expliquer pourquoi la valeur $A(m,n,k)$ est bien calculée par cet algorithme. \textbf{(2)} Expliquer pourquoi l'algorithme qu'on a écrit en (1) est primitif récursif (on pourra prendre connaissance des conclusions de l'exercice \ref{exercise-arrays-for-p-r-functions}). \textbf{(3)} En déduire que la fonction $B$ est primitive récursive. (Autrement dit, on ne peut pas calculer $A$ par un algorithme p.r., mais on peut \emph{vérifier} sa valeur, si elle est donnée en entrée, par un tel algorithme.) \begin{corrige} \textbf{(1)} On commence par remarquer que les « petites valeurs » $m\leq 1$ ou $n\leq 1$ de la fonction d'Ackermann, se calculent facilement par des formules de l'énoncé. L'algorithme calculant $A(m,n,k)$ est alors le suivant. Si $m\leq 1$ ou $n\leq 1$ on peut facilement calculer la valeur comme on vient de l'expliquer, donc on se place dans le cas $m \geq 2$ et $n \geq 2$. (Notons aussi que toute valeur de la fonction d'Ackermann pour $m\geq 1$ est non nulle, ce qui nous permet d'utiliser $0$ pour représenter « non calculé » dans le tableau.) On initialise un tableau $\tau$ de deux indices, $i,\ell$, initialement rempli de $0$, qui servira à stocker les valeurs de la fonction d'Ackermann $A(m,i,\ell)$. Pour chaque $\ell$ allant de $0$ à $k$ et chaque $i$ allant de $0$ à $b$, on calcule $A(m,i,\ell)$ de la manière suivante : si $i\leq 1$ ou $\ell=0$ on utilise la formule évoquée ci-dessus et stocke la valeur dans le tableau ; sinon, on consulte le tableau en $(i-1,\ell)$ et, si cette valeur $u$ est définie (c'est-à-dire non nulle), on consulte le tableau en $(u,\ell-1)$ et, si cette valeur $w$ est définie, on la stocke dans le tableau en $(i,\ell)$. Autrement dit : \begin{itemize} \item si $m\leq 1$ ou $n\leq 1$, calculer facilement $A(m,n,k)$ et renvoyer sa valeur ; sinon : \item initialiser un tableau $\tau$ (d'indices $i$ allant de $0$ à $b$ et $\ell$ allant de $0$ à $k$, et initialement rempli de $0$), \item pour $\ell$ allant de $0$ à $k$, \begin{itemize} \item pour $i$ allant de $0$ à $b$, \begin{itemize} \item si $i\leq 1$ ou $\ell=0$, calculer facilement $w := A(m,i,\ell)$ et stocker $\tau(i,\ell) \leftarrow w$, \item sinon, consulter $u := \tau(i-1,\ell)$, \item si $u \neq 0$, consulter $w := \tau(u,\ell-1)$, \item si $w \neq 0$, stocker $\tau(i,\ell) \leftarrow w$. \end{itemize} \end{itemize} \item finalement : renvoyer $\tau(k,n)$ si elle est $>0$, sinon « échec ». \end{itemize} En Python, avec de petites variations : {\tt \noindent def ackermann\_small(m,n,k):\\ \strut\quad \# Returns A(m,n,k) value if m<=1 or n<=1 or k<=2\\ \strut\quad if k==0: return m+n\\ \strut\quad if k==1: return m*n\\ \strut\quad if k==2: return m**n\\ \strut\quad if n==0: return 1\\ \strut\quad if n==1: return m\\ \strut\quad if m==0: return (n+1)\%2\\ \strut\quad if m==1: return 1\\ \\ def ackermann\_bounded(m,n,k,b):\\ \strut\quad \# Returns A(m,n,k) (at least) if its value is <=b\\ \strut\quad if m<=1 or n<=1: return ackermann\_small(m,n,k)\\ \strut\quad tab = \{\}\\ \strut\quad for l in range(k+1):\\ \strut\quad \strut\quad for i in range(b+1):\\ \strut\quad \strut\quad \strut\quad if l==0 or i<=1:\\ \strut\quad \strut\quad \strut\quad \strut\quad w = ackermann\_small(m,i,l)\\ \strut\quad \strut\quad \strut\quad \strut\quad tab[(i,l)] = w\\ \strut\quad \strut\quad \strut\quad else:\\ \strut\quad \strut\quad \strut\quad \strut\quad if (i-1,l) in tab:\\ \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad u = tab[(i-1,l)]\\ \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad if (u,l-1) in tab:\\ \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad w = tab[(u,l-1)]\\ \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad tab[(i,l)] = w\\ \strut\quad if (n,k) in tab:\\ \strut\quad \strut\quad return tab[(n,k)] } L'algorithme repose sur la formule $A(m,i,\ell) = A(m,A(m,i-1,\ell),\ell-1)$ (qui est une simple réécriture de la troisième ligne de la définition), où on a appelé $u = A(m,i-1,\ell)$ et $w = A(m,u,\ell-1)$ : cete formule montre que si les valeurs $(i-1,\ell)$ et $(u,\ell-1)$ sont trouvées dans le tableau, la valeur $A(m,i,\ell)$ sera correctement calculée. Or on montre par récurrence sur $\ell$ et $i$ que toutes les valeurs pour lesquelles $A(m,i,\ell) \leq b$ (ou bien $i\leq 1$ ou $\ell=0$) seront effectivement calculées par l'algorithme : en effet, si $A(m,i,\ell) \leq b$, alors par la croissance en la deuxième variable de la fonction d'Ackermann, $u := A(m,i-1,\ell)$ est lui-même $\leq b$ (ou alors $i=1$), donc aura été correctement calculé avant $A(m,i,\ell)$, et $A(m,u,\ell-1)$ aura été calculé et stocké dans le tableau puisque la boucle sur $\ell$ est extérieure à celle sur $i$ et que la valeur $u$ est dans les bornes de la boucle sur $i$. En particulier, si $b$ est un majorant de la valeur $A(m,n,k)$ qu'on cherchait, alors l'algorithme renvoie $A(m,n,k)$. \textbf{(2)} L'algorithme qu'on a décrit ci-dessus ne fait aucun appel récursif et n'utilise que des boucles bornées (deux boucles imbriquées). L'utilisation d'un tableau est justifiée par l'exercice \ref{exercise-arrays-for-p-r-functions}. On a donc bien défini une fonction primitive récursive. \textbf{(3)} L'algorithme qu'on a décrit calcule de façon primitive récursive en $m,n,k,b$ la valeur $A(m,n,k)$ si tant est que celle-ci est $\leq b$. En particulier, pour calculer $B(m,n,k,v)$ il suffit d'appliquer cet algorithme à $m,n,k,v$ (c'est-à-dire avec $v$ lui-même comme borne) et, s'il renvoie une valeur $w$, tester si $v=w$ : si c'est le cas on renvoie « oui » (enfin, $1$), sinon, ou si l'algorithme n'a pas réussi à caluler $A(m,n,k)$ on renvoie « non » (enfin, $0$). La fonction $B$ est donc primitive récursive. (On dit parfois abusivement que la fonction d'Ackermann a un graphe primitif récursif pour dire que la fonction indicatrice de son graphe est primitive récursive. On comparera à l'exercice \ref{exercise-computable-graph} d'après lequel une fonction dont la fonction indicatrice du graphe est calculable, i.e., générale récursive, est elle-même calculable, i.e., générale récursive.) \end{corrige} % \exercice\ (${\star}{\star}$)\par\nobreak On dira que deux parties $L,M$ de $\mathbb{N}$ disjointes (c'est-à-dire $L\cap M = \varnothing$) sont \textbf{calculablement séparables} lorsqu'il existe un $E \subseteq \mathbb{N}$ décidable tel que $L \subseteq E$ et $M \subseteq \complement E$ (où $\complement E$ désigne le complémentaire de $E$) ; dans le cas contraire, on les dit \textbf{calculablement inséparables}. \textbf{(1)} Expliquer pourquoi deux ensembles $L,M \subseteq \mathbb{N}$ disjoints sont calculablement séparables si et seulement s'il existe un algorithme qui, prenant en entrée un élément $x$ de $\mathbb{N}$ : \begin{itemize} \item termine toujours en temps fini, \item répond « vrai » si $x\in L$ et « faux » si $x \in M$ (rien n'est imposé si $x\not\in L\cup M$). \end{itemize} \textbf{(2)} Expliquer pourquoi deux ensembles \emph{décidables} disjoints sont toujours calculablement séparables. On cherche maintenant à montrer qu'il existe deux ensembles $L,M \subseteq \mathbb{N}$ \emph{semi-décidables} disjoints et calculablement \emph{in}séparables. Pour cela, on appelle $L := \{\langle e,x\rangle : \varphi_e(x){\downarrow} = 1\}$ l'ensemble des codes des couples $\langle e,x\rangle$ formés d'un programme (=algorithme) $e$ et d'une entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$ termine en temps fini et renvoie la valeur $1$ ; et $M := \{\langle e,x\rangle : \varphi_e(x){\downarrow} = 2\}$ l'ensemble défini de la même manière mais avec la valeur $2$. \textbf{(3)} Pourquoi $L$ et $M$ sont-ils disjoints ? \textbf{(4)} Pourquoi $L$ et $M$ sont-ils semi-décidables ? \textbf{(5)} En imitant la démonstration du théorème de Turing sur l'indécidabilité du problème de l'arrêt, ou bien en utilisant le théorème de récursion de Kleene, montrer qu'il n'existe aucun algorithme qui, prenant en entrée le code d'un couple $\langle e,x\rangle$, termine toujours en temps fini et répond « vrai » si $\langle e,x\rangle\in L$ et « faux » si $\langle e,x\rangle \in M$ (\emph{indication :} si un tel algorithme existait, on pourrait s'en servir pour faire le contraire de ce qu'il prédit). \textbf{(6)} Conclure. \begin{corrige} \textbf{(1)} Si $E$ est décidable tel que $L \subseteq E$ et $M \subseteq \complement E$, alors un algorithme qui décide $E$ (c'est-à-dire, quand on lui fournit l'entrée $x$, répond « vrai » si $x\in E$, et « faux » si $x \not\in E$) répond bien aux critères demandés. Réciproquement, donné un algorithme qui répond aux critères demandés, si $E$ est l'ensemble des $x$ sur lesquels il répond « vrai », alors $E$ est bien décidable (on peut toujours modifier l'algorithme si nécessaire pour qu'il ne réponde que « vrai » ou « faux »), et on a $L \subseteq E$ et $M \subseteq \complement E$. \textbf{(2)} Si $L,M$ sont décidables disjoints, on peut poser $E = L$, qui est décidable et vérifie à la fois $L \subseteq E$ (trivialement) et $M \subseteq \complement E$ (c'est une reformulation du fait que $M$ est disjoint de $E=L$). \textbf{(3)} Comme $L$ est l'ensemble des codes des couples $\langle e,x\rangle$ tels que $\varphi_e(x) = 1$ et $M$ l'ensemble des codes des couples $\langle e,x\rangle$ tels que $\varphi_e(x) = 2$, aucun élément ne peut appartenir aux deux, c'est-à-dire qu'ils sont disjoints. \textbf{(4)} Pour semi-décider si le code d'un couple $\langle e,x\rangle$ appartient à $L$, il suffit de lancer l'exécution du programme $e$ sur l'entrée $x$ et, si elle termine en retournant $1$, renvoyer « vrai », tandis que si elle termine en renvoyant n'importe quelle autre valeur, faire une boucle infinie (bien sûr, si le programme $e$ ne termine jamais sur l'entrée $x$, on ne termine pas non plus). Ceci montre que $L$ est semi-décidable. Le même raisonnement s'applique pour $M$. \textbf{(5)} Supposons par l'absurde qu'il existe un algorithme $g$ comme annoncé (i.e., qui prend $\langle e,x\rangle$ en entrée, termine toujours, et renvoie « vrai » si $\langle e,x\rangle\in L$ et « faux » si $\langle e,x\rangle \in M$). Définissons un nouvel algorithme qui, donné un entier $e$, effectue les calculs suivants : (1º) interroger l'algorithme $g$ supposé exister en lui fournissant le code du couple $\langle e,e\rangle$ comme entrée, et ensuite (2º) si $g$ répond vrai, renvoyer la valeur $2$, tandis que si $g$ répond n'importe quoi d'autre, renvoyer la valeur $1$. L'algorithme qui vient d'être décrit aurait un certain numéro, disons, $c$, et la description de l'algorithme fait qu'il termine toujours, que la valeur $\varphi_c(e)$ qu'il renvoie vaut toujours soit $1$ soit $2$, et qu'elle vaut $2$ si $\langle e,e\rangle \in L$ (c'est-à-dire si $\varphi_e(e) = 1$) et $1$ si $\langle e,e\rangle \in M$ (c'est-à-dire si $\varphi_e(e) = 2$). En particulier, en prenant $e=c$, on voit que $\varphi_c(c)$ doit valoir $1$ ou $2$, doit valoir $2$ si $\varphi_c(c) = 1$ et $1$ si $\varphi_c(c) = 2$, ce qui est une contradiction. \emph{Variante :} La preuve ci-dessus a été rédigée en explicitant l'argument diagonal. On peut aussi, si on préfère, utiliser le théorème de récursion de Kleene. L'argument est alors le suivant. Supposons par l'absurde qu'il existe un algorithme $g$ comme annoncé (i.e., qui prend $\langle e,x\rangle$ en entrée, termine toujours, et renvoie « vrai » si $\langle e,x\rangle\in L$ et « faux » si $\langle e,x\rangle \in M$). Définissons un nouvel algorithme qui, donné un couple $(e,x)$, effectue les calculs suivants : (1º) interroger l'algorithme $g$ supposé exister en lui fournissant le code $\langle e,x\rangle$ comme entrée, et ensuite (2º) si $g$ répond vrai, renvoyer la valeur $2$, tandis que si $g$ répond n'importe quoi d'autre, renvoyer la valeur $1$. On obtient ainsi une fonction $h$ calculable totale $\mathbb{N}^2 \to \{1,2\}$ telle que $h(e,x) = 2$ lorsque $\langle e,x\rangle\in L$ et $h(e,x) = 1$ lorsque $\langle e,x\rangle\in M$. Le théorème de récursion de Kleene assure qu'il existe $e$ tel que $\varphi_e(x) = h(e,x)$ pour tout $x$, et notamment, quelle que soit $x$ la valeur $\varphi_e(x)$ et définie et vaut soit $1$ soit $2$, et elle vaut $2$ si $\langle e,x\rangle \in L$ (c'est-à-dire si $\varphi_e(x) = 1$) et $1$ si $\langle e,x\rangle \in M$ (c'est-à-dire si $\varphi_e(x) = 2$). Ceci est une contradiction. \textbf{(6)} La question (5) montre (compte tenu de la question (1)) que $L$ et $M$ ne sont pas calculablement séparables, i.e.., sont calculablement inséparables, tandis que (3) et (4) montrent que $L$ et $M$ sont disjoints et semi-décidables. On a donc bien montré l'existence d'ensembles semi-décidables disjoints et calculablement inséparables. \end{corrige} % % % \section{\texorpdfstring{$\lambda$}{Lambda}-calcul non typé} \exercice\ (${\star}$)\par\nobreak Pour chacun des termes suivants du $\lambda$-calcul non typé, dire s'il est en forme normale, ou en donner la forme normale s'il y en a une. \textbf{(a)} $(\lambda x.x)(\lambda x.x)$ \hskip 1emplus1emminus1em \textbf{(b)} $(\lambda x.xx)(\lambda x.x)$ \hskip 1emplus1emminus1em \textbf{(c)} $(\lambda x.xx)(\lambda x.xx)$ \hskip 1emplus1emminus1em \textbf{(d)} $(\lambda xx.x)(\lambda xx.x)$ \hskip 1emplus1emminus1em \textbf{(e)} $(\lambda xy.x)(\lambda xy.x)$ \hskip 1emplus1emminus1em \textbf{(f)} $(\lambda xy.xy)y$ \hskip 1emplus1emminus1em \textbf{(g)} $(\lambda xy.xy)(\lambda xy.xy)$ \begin{corrige} \textbf{(a)} $(\lambda x.x)(\lambda x.x) \rightarrow_\beta \lambda x.x$ \hskip 1emplus1emminus1em \textbf{(b)} $(\lambda x.xx)(\lambda x.x) \rightarrow_\beta (\lambda x.x)(\lambda x.x) \rightarrow_\beta \lambda x.x$ \hskip 1emplus1emminus1em \textbf{(c)} $(\lambda x.xx)(\lambda x.xx) \rightarrow_\beta (\lambda x.xx)(\lambda x.xx) \rightarrow_\beta \cdots$ la seule $\beta$-réduction possible boucle donc il n'y a pas de forme normale. \hskip 1emplus1emminus1em \textbf{(d)} On renomme d'abord les variables liées en se rappelant que chaque variable est liée par le $\lambda$ le plus \emph{intérieur} sur son nom : $(\lambda xx.x)(\lambda xx.x) = (\lambda x.\lambda x.x)(\lambda x.\lambda x.x) \mathrel{\equiv_\alpha} (\lambda x.\lambda y.y)(\lambda u.\lambda v.v) \rightarrow_\beta \lambda y.y \mathrel{\equiv_\alpha} \lambda x.x$ \hskip 1emplus1emminus1em \textbf{(e)} $(\lambda xy.x)(\lambda xy.x) = (\lambda x.\lambda y.x)(\lambda x.\lambda y.x) \rightarrow_\beta \lambda y.\lambda x.\lambda y.x \mathrel{\equiv_\alpha} \lambda y.\lambda x.\lambda z.x = \lambda yxz.x$ \hskip 1emplus1emminus1em \textbf{(f)} $(\lambda xy.xy)y = (\lambda x.\lambda y.xy)y$ ici pour faire la $\beta$-réduction on doit d'abord renommer la variable liée par le second $\lambda$ pour éviter qu'elle capture le $y$ libre : $(\lambda x.\lambda y.xy)y \mathrel{\equiv_\alpha} (\lambda x.\lambda z.xz)y \rightarrow_\beta \lambda z.yz$ (le piège serait de répondre $\lambda y.yy$ ici !) \hskip 1emplus1emminus1em \textbf{(g)} $(\lambda xy.xy)(\lambda xy.xy) = (\lambda x.\lambda y.xy)(\lambda x.\lambda y.xy) \rightarrow_\beta \lambda y.(\lambda x.\lambda y.xy)y \mathrel{\equiv_\alpha} \lambda y.(\lambda x.\lambda z.xz)y \rightarrow_\beta \lambda y.\lambda z.yz = \lambda yz.yz \mathrel{\equiv_\alpha} \lambda xy.xy$ \end{corrige} % \exercice\ (${\star}{\star}$)\par\nobreak \textbf{(1)} Considérons le terme $T_2 := (\lambda x.xxx)(\lambda x.xxx)$ du $\lambda$-calcul non typé. Étudier le graphe des $\beta$-réductions dessus, c'est-à-dire tous les termes obtenus par $\beta$-réduction à partir de $T_2$, et les $\beta$-réductions entre eux. \textbf{(2)} Que se passe-t-il pour $V := (\lambda x.x(xx))(\lambda x.x(xx))$ ? Sans entrer dans les détails, on donnera quelques chemins de $\beta$-réduction, notamment celui suivi par la réduction extérieure gauche. \textbf{(3)} Étudier de façon analogue le comportement du terme $R := (\lambda x.\lambda v.xxv) (\lambda x.\lambda v.xxv)$ sous l'effet de la $\beta$-réduction. \begin{corrige} \textbf{(1)} La $\beta$-réduction du seul redex de $T_2$ s'écrit $(\lambda x.xxx)(\lambda x.xxx) \rightarrow (\lambda x.xxx)(\lambda x.xxx)(\lambda x.xxx)$. Appelons $T_3$ le terme en question, et plus généralement $T_n$ le terme $(\lambda x.xxx)\cdots (\lambda x.xxx)$ avec $n-1$ applications sur $(\lambda x.xxx)$ de $(\lambda x.xxx)$ (donc $n$ fois ce sous-terme au total) ; on se rappellera bien que les parenthèses sont vers la \emph{gauche}, c'est-à-dire que $T_4$ est $((T_1 T_1)T_1)T_1$ par exemple. Il y a un \emph{unique} redex dans $T_n$ (bien qu'il y ait $n$ lambdas, un seul est appliqué), à savoir celui des deux $T_1$ les plus à gauche (ou les plus profondément imbriqués) : la seule $\beta$-réduction possible consiste à remplacer ce redex $T_1 T_1$ (soit $T_2$) par son réduit $(T_1 T_1) T_1$ (soit $T_3$), ce qui donne $T_{n+1}$. Le graphe des $\beta$-réductions est donc $T_2 \rightarrow T_3 \rightarrow T_4 \rightarrow \cdots$ avec une unique $\beta$-réduction possible à chaque fois. Le terme n'est pas faiblement (ni à plus forte raison fortement) normalisable. \textbf{(2)} La $\beta$-réduction du seul redex donne $(\lambda x.x(xx))(\lambda x.x(xx)) \rightarrow (\lambda x.x(xx))((\lambda x.x(xx))(\lambda x.x(xx)))$. Notant $U := \lambda x.x(xx)$ pour y voir plus clair, on a donc $V := UU \rightarrow U(UU)$. Maintenant on a deux possibilités de redex à réduire : le redex extérieur $U(UU)$ formé par l'expression tout entière, et le redex intérieur $UU$. Le redex extérieur $U(UU)$ se réduit en $(UU)((UU)(UU))$ (qui a maintenant trois redex), tandis que la réduction du redex intérieur $UU$ dans $U(UU)$ donne $U(U(UU))$. Il est alors facile de construire toutes sortes de chemins de $\beta$-réductions en se rappelant que tout $UX$ est un redex, avec pour réduit $X(XX)$. On peut notamment distinguer la réduction intérieure gauche (ou droite, ici elles coïncident) \[ UU \rightarrow U(UU) \rightarrow U(U(UU)) \rightarrow U(U(U(UU))) \rightarrow U(U(U(U(UU)))) \cdots \] et la réduction extérieure gauche (on utilise $V := UU$ pour plus de clarté ; mais on gardera bien à l'esprit que $V$, contrairement à $U$, n'est pas une abstraction donc ne forme pas un redex quand on l'applique, par contre c'est lui-même un redex qui se réduit en $UV$) \[ \begin{aligned} UU := V &\rightarrow UV \rightarrow V(VV) \rightarrow (UV)(VV) \rightarrow (V(VV))(VV)\\ &\rightarrow ((UV)(VV))(VV) \rightarrow ((VV)(VV))(VV) \rightarrow \cdots \end{aligned} \] ou encore la réduction extérieure droite \[ \begin{aligned} UU := V &\rightarrow UV \rightarrow V(VV) \rightarrow V(V(UV)) \rightarrow V(V(V(VV)))\\ &\rightarrow V(V(V(V(UV)))) \rightarrow V(V(V(V(V(VV))))) \rightarrow \cdots \end{aligned} \] Aucun de ces chemins ne termine (on a vu en cours que si la réduction extérieure gauche ne termine pas, aucun chemin de $\beta$-réductions ne termine, mais ici c'est clair car une $\beta$-réduction ne peut de toute façon qu'augmenter le nombre de $U$ dans l'expression). (Seule la notion de réduction extérieure gauche a été définie en cours ; on peut néanmoins définir sans difficulté les quatre réductions extérieure gauche, intérieure gauche, extérieure droite et intérieure droite : le redex extérieur gauche est celui dont le bord gauche est le plus à gauche, le redex intérieur gauche est celui dont le bord droit est le plus à gauche, le redex extérieur droite est celui dont le bord droit est le plus à droite, et le redex intérieur droite est celui dont le bord gauche est le plus à droite. Peu importent ces définitions, cependant, ici le but est simplement d'illustrer quelques chemins possibles.) (\emph{Remarque :} Je n'ai pas réfléchi à trouver une caractérisation de tous les termes en lesquels $UU$ peut se réduire, mais on peut les décrire comme des arbres d'application avec $U$ aux feuilles, et la $\beta$-réduction se voir alors comme une transformation simple sur les arbres.) \textbf{(3)} La $\beta$-réduction du seul redex de $R$ s'écrit $(\lambda x.\lambda v.xxv) (\lambda x.\lambda v.xxv) \rightarrow \lambda v.(\lambda x.\lambda v.xxv)(\lambda x.\lambda v.xxv)v = \lambda v. R v$. On peut alors continuer ainsi : $R \rightarrow \lambda v. Rv \rightarrow \lambda v. (\lambda v. Rv)v \rightarrow \lambda v. (\lambda v. (\lambda v. Rv)v)v \rightarrow \cdots$. Même si ces écritures sont correctes (rappelons que chaque variable est liée par le $\lambda$ le plus \emph{intérieur} sur son nom), il est considérablement plus clair de renommer les variables liées, par exemple ainsi : \[ R \rightarrow \lambda v_1. Rv_1 \rightarrow \lambda v_1. (\lambda v_2. Rv_2)v_1 \rightarrow \lambda v_1. (\lambda v_2. (\lambda v_3. Rv_3)v_2)v_1 \rightarrow \cdots \] (on prendra garde à ne pas confondre le troisième terme de cette suite, par exemple, avec $\lambda v_1. \lambda v_2. Rv_2v_1$ qui désigne $\lambda v_1. \lambda v_2. (Rv_2v_1)$ et qui peut s'écrire $\lambda v_1 v_2. Rv_2v_1$ : ce n'est pas du tout la même chose !). \end{corrige} % \exercice\label{exercise-traduction-entiers-de-church}\ (${\star}{\star}{\star}$)\par\nobreak On considère la traduction évidente des termes du $\lambda$-calcul en langage Python et/ou en Scheme définie de la manière suivante : \begin{itemize} \item une variable se traduit en elle-même (i.e., en l'identificateur de ce nom), \item une application $(P Q)$ du $\lambda$-calcul se traduit par $\mathtt{P}(\mathtt{Q})$ pour le Python et par $(\mathtt{P}\ \mathtt{Q})$ pour le Scheme (dans les deux cas, c'est la notation pour l'application d'une fonction à un terme), où $\mathtt{P},\mathtt{Q}$ sont les traductions de $P,Q$ respectivement, \item une abstraction $\lambda v. E$ du $\lambda$-calcul se traduit par $\texttt{(lambda $\mathtt{v}$: $\mathtt{E}$)}$ en Python et $\texttt{(lambda ($\mathtt{v}$) $\mathtt{E}$)}$ en Scheme (dans les deux cas, c'est la notation pour la création d'une fonction anonyme), où $\mathtt{E}$ est la traduction de $E$ et $\mathtt{v}$ l'identificateur ayant pour nom celui de la variable $v$. \end{itemize} \textbf{(a)} Traduire les entiers de Church $\overline{0}, \overline{1}, \overline{2}, \overline{3}$ en Python et en Scheme. \textbf{(b)} Écrire une fonction dans chacun de ces langages prenant en entrée (la conversion d')un entier de Church et renvoyant l'entier natif (c'est-à-dire au sens usuel du langage) correspondant. On pourra pour cela utiliser la fonction successeur qui s'écrit $\texttt{(lambda n: n+1)}$ en Python et $\texttt{(lambda (n) (+ n 1))}$ en Scheme. \textbf{(c)} Traduire les fonctions $\lambda mnfx.nf(mfx)$, $\lambda mnf.n(mf)$ et $\lambda mn.nm$ qui représentent $(m,n)\mapsto m+n$, $(m,n)\mapsto mn$ et $(m,n)\mapsto m^n$ sur les entiers de Church en Python et en Scheme, et vérifier leur bon fonctionnement sur quelques exemples (en utilisant la fonction écrite en (b) pour décoder le résultat). \textbf{(d)} Traduire le terme non-normalisable $(\lambda x.xx) (\lambda x.xx)$ en Python et Scheme : que se passe-t-il quand on le fait exécuter à un interpréteur de ces langages ? Expliquer brièvement cette différence. \textbf{(e)} Proposer une tentative de traduction des termes du $\lambda$-calcul en OCaml ou Haskell : reprendre les questions précédentes en indiquant ce qui change pour ces langages. \begin{corrige} \textbf{(a)} En Python : $\overline{0}$ devient \texttt{lambda f: lambda x: x}, $\overline{1}$ devient \texttt{lambda f: lambda x: f(x)}, $\overline{2}$ devient \texttt{lambda f: lambda x: f(f(x))} (chacun sur une ligne) et $\overline{3}$ devient \texttt{lambda f: lambda x: f(f(f(x)))} (chacun sur une ligne). En Scheme : $\overline{0}$ devient \texttt{(lambda (f) (lambda (x) x))}, $\overline{1}$ devient \texttt{(lambda (f) (lambda (x) (f x)))}, $\overline{2}$ devient \texttt{(lambda (f) (lambda (x) (f (f x))))} et $\overline{3}$ devient \texttt{(lambda (f) (lambda (x) (f (f (f x)))))} (espacement indifférent mais les parenthèses sont critiques). \textbf{(b)} Pour convertir un entier de Church en entier natif, il suffit d'itérer la fonction successeur la nombre de fois représenté par l'entier de Church, ce que l'entier de Church permet justement de faire, en l'appliquant au final à $0$. En Python, cela donne : \texttt{def fromchurch(ch): return (ch (lambda n: n+1))(0)} (ou \texttt{fromchurch = lambda ch: (ch (lambda n: n+1))(0)} mais dans tous les cas sur une seule ligne) ; en Scheme : \texttt{(define (fromchurch ch) ((ch (lambda (n) (+ n 1))) 0))} ce qui est du sucre syntaxique pour \texttt{(define fromchurch (lambda (ch) ((ch (lambda (n) (+ n 1))) 0)))}. \textbf{(c)} Voici un exemple de code vérifiant que $2+3=5$, que $2\times 3=6$ et que $2^3=8$ sur les entiers de Church, d'abord en Python : \noindent\texttt{% churchzero = (lambda f: lambda x: x)\\ churchone = (lambda f: lambda x: f(x))\\ churchtwo = (lambda f: lambda x: f(f(x)))\\ churchthree = (lambda f: lambda x: f(f(f(x))))\\ fromchurch = lambda ch: (ch (lambda n: n+1))(0)\\ churchadd = lambda m: lambda n: lambda f: lambda x: (n(f))((m(f))(x))\\ churchmul = lambda m: lambda n: lambda f: n(m(f))\\ churchpow = lambda m: lambda n: n(m)\\ \# Check 2+3 == 5:\\ fromchurch((churchadd(churchtwo))(churchthree))\\ \# Check 2*3 == 6:\\ fromchurch((churchmul(churchtwo))(churchthree))\\ \# Check 2\textasciicircum 3 == 8:\\ fromchurch((churchpow(churchtwo))(churchthree)) } \noindent …puis en Scheme : \noindent\texttt{% (define churchzero (lambda (f) (lambda (x) x)))\\ (define churchone (lambda (f) (lambda (x) (f x))))\\ (define churchtwo (lambda (f) (lambda (x) (f (f x)))))\\ (define churchthree (lambda (f) (lambda (x) (f (f (f x))))))\\ (define fromchurch (lambda (ch) ((ch (lambda (n) (+ n 1))) 0)))\\ (define churchadd (lambda (m) (lambda (n) (lambda (f) (lambda (x)\\ \ \ ((n f) ((m f) x)))))))\\ (define churchmul (lambda (m) (lambda (n) (lambda (f) (n (m f))))))\\ (define churchpow (lambda (m) (lambda (n) (n m))))\\ ;; Check 2+3 == 5:\\ (fromchurch ((churchadd churchtwo) churchthree))\\ ;; Check 2*3 == 6:\\ (fromchurch ((churchmul churchtwo) churchthree))\\ ;; Check 2\textasciicircum 3 == 8:\\ (fromchurch ((churchpow churchtwo) churchthree)) } Dans les deux cas, les valeurs retournées sont successivement $5$, $6$ et $8$. Noter que dans les deux langages la syntaxe est rendue lourdingue par le fait que (conformément aux conventions du $\lambda$-calcul dont on a mécaniquement traduit des termes) on ne crée que des fonctions d'\emph{un} argument, ce qui oblige les fonctions d'opération à prendre les arguments sous forme « curryfiée ». Il serait bien plus naturel d'écrire par exemple \texttt{churchpow = lambda m,n: n(m)} en Python et \texttt{(define churchpow (lambda (m n) (n m)))} en Scheme pour définir directement une fonction de \emph{deux} arguments, qu'on peut ensuite utiliser comme \texttt{churchpow(churchtwo,churchthree)} et \texttt{(churchpow churchtwo churchthree)} respectivement. \texttt{(d)} En Python : $\texttt{(lambda x: x(x))(lambda x: x(x))}$ ; en Scheme : \texttt{((lambda (x) (x x)) (lambda (x) (x x)))}. Le premier termine rapidement avec un débordement de pile (au moins dans la version actuelle Python 3.11), le second, quel que soit l'interpréteur Scheme (au moins tous ceux que j'ai pu tester), boucle indéfiniment (mais sans consommation de pile supplémentaire ni d'autre forme de mémoire). La raison de cette différence est que Scheme effectue (et la spécification du langage impose) une \emph{récursion terminale propre} : lorsque le code d'une fonction $f$ termine par l'appel à une autre fonction $g$ (en renvoyant sa valeur), le contrôle de l'exécution est simplement passé de $f$ à $g$ sans empilement d'adresse de retour (qui n'a pas lieu d'être puisque la valeur de retour de $f$ sera justement celle de $g$) ; en Python, en revanche, la récursion terminale n'est pas traitée spécialement, donc chaque appel à \texttt{x(x)} est empilé et jamais dépilé et la pile déborde rapidement. \texttt{(e)} La traduction du $\lambda$-calcul en OCaml ou Haskell est évidente en utilisant $\texttt{fun $\mathtt{v}$ -> $\mathtt{E}$}$ (noté $\texttt{\textbackslash $\mathtt{v}$ -> $\mathtt{E}$}$ en Haskell) pour traduire $\lambda v.E$ (et toujours $(\mathtt{P}\ \mathtt{Q})$ pour $(P Q)$). Néanmoins, il n'est pas évident qu'on puisse toujours écrire les termes qu'on souhaite, parce qu'ils ne seront pas forcément typables. En OCaml, le test sur les entiers de Church donne : \noindent\texttt{% let churchzero = fun f -> fun x -> x\\ let churchone = fun f -> fun x -> f x\\ let churchtwo = fun f -> fun x -> f (f x)\\ let churchthree = fun f -> fun x -> f (f (f x))\\ let fromchurch = fun ch -> ch (fun n->(n+1)) 0\\ let churchadd = fun m -> fun n -> fun f -> fun x -> (n f)(m f x)\\ let churchmul = fun m -> fun n -> fun f -> n (m f)\\ let churchpow = fun m -> fun n -> n m\\ ;;\\ (* Check 2+3 == 5: *)\\ fromchurch(churchadd churchtwo churchthree) ;;\\ (* Check 2*3 == 6: *)\\ fromchurch(churchmul churchtwo churchthree) ;;\\ (* Check 2\textasciicircum 3 == 8: *)\\ fromchurch(churchpow churchtwo churchthree) ;; } \noindent …et en Haskell : \noindent\texttt{% let churchzero = \textbackslash f -> \textbackslash x -> x\\ let churchone = \textbackslash f -> \textbackslash x -> f x\\ let churchtwo = \textbackslash f -> \textbackslash x -> f (f x)\\ let churchthree = \textbackslash f -> \textbackslash x -> f (f (f x))\\ let fromchurch = \textbackslash ch -> ch (\textbackslash n->(n+1)) 0\\ let churchadd = \textbackslash m -> \textbackslash n -> \textbackslash f -> \textbackslash x -> (n f)(m f x)\\ let churchmul = \textbackslash m -> \textbackslash n -> \textbackslash f -> n (m f)\\ let churchpow = \textbackslash m -> \textbackslash n -> n m\\ -- Check 2+3 == 5:\\ fromchurch(churchadd churchtwo churchthree)\\ -- Check 2*3 == 6:\\ fromchurch(churchmul churchtwo churchthree)\\ -- Check 2\textasciicircum 3 == 8:\\ fromchurch(churchpow churchtwo churchthree) } Il se trouve que sur ces exemples simples le typage n'empêche pas la construction, mais si on essayait de faire la fonction $n \mapsto n^n$, par exemple, la fonction \texttt{fun n -> churchpow n n} ne type pas. De même, le terme non normalisant de la question (d), qui se traduirait \texttt{(fun x -> x x)(fun x -> x x)} en OCaml, et \texttt{(\textbackslash x -> x x)(\textbackslash x -> x x)} en Haskell, est refusé par le système de typage : ni le OCaml ni le Haskell ne permet de traduire tous les termes du $\lambda$-calcul non typé, précisément parce qu'ils sont typés. (\textbf{Attention :} si le Python comme le Scheme permettent de \emph{traduire} tous les termes du $\lambda$-calcul non typé, le comportement de l'évaluateur, dans les deux cas, ne correspond pas forcément à une stratégie évidente de $\beta$-réduction du $\lambda$-calcul. Notamment, le terme $(\lambda uz.z)((\lambda x.xx)(\lambda x.xx))$, bien que faiblement normalisable en $\lambda$-calcul, conduira une fois traduit à une boucle dans ces deux langages, parce que l'évaluateur commence par évaluer les arguments d'une fonction avant d'appliquer la fonction ; inversement, le terme $\lambda u.(\lambda x.xx)(\lambda x.xx)$, bien qu'il ne soit même pas faiblement normalisable en $\lambda$-calcul, est accepté sans broncher par ces deux langages car le corps d'une fonction n'est évalué qu'à l'application de la fonction. Cependant, les calculs de fonctions primitives récursives sur les entiers de Church ne font intervenir que des termes fortement normalisants sur lesquels ces difficultés ne se posent pas.) \end{corrige} % \exercice\ (${\star}{\star}$)\par\nobreak On s'intéresse à une façon d'implémenter les couples en $\lambda$-calcul non-typé : $\Pi := \lambda xyf.fxy$ (servant à faire un couple) et $\pi_1 := \lambda p.p(\lambda xy.x)$ et $\pi_2 := \lambda p.p(\lambda xy.y)$ (servant à en extraire la première et la seconde composantes). \textbf{(1)} Montrer que, pour tous termes $X,Y$, le terme $\pi_1(\Pi XY)$ se $\beta$-réduit en $X$ et $\pi_2(\Pi XY)$ se $\beta$-réduit en $Y$. \textbf{(2)} Expliquer intuitivement comment fonctionnent $\Pi$, $\pi_1$, $\pi_2$ : comment est représentée le couple $(x,y)$ par $\Pi$ (c'est-à-dire $\Pi xy$) ? \textbf{(3)} Écrire les fonctions $\Pi$, $\pi_1$, $\pi_2$ (on pourra les appeler par exemple \texttt{pairing}, \texttt{proj1}, \texttt{proj2}) dans un langage de programmation fonctionnel (on pourra prendre connaissance de l'énoncé de l'exercice \ref{exercise-traduction-entiers-de-church}), et vérifier leur bon fonctionnement. (Mieux vaut, ici, choisir un langage fonctionnel non typé, c'est-à-dire dynamiquement typé, pour mieux refléter le $\lambda$-calcul non typé et éviter d'éventuels tracas liés au typage. Si le langage a des couples natifs, on pourra écrire des conversions des couples natifs dans le codage défini ici, et vice versa.) Si on a des notions de compilation : sous quelle forme est stockée l'information du couple dans la représentation faite par $\Pi$ ? \begin{corrige} \textbf{(1)} Effectuons par exemple la $\beta$-réduction extérieure gauche (mais on rappelle que le théorème de Church-Rosser affirme que la normalisation est confluente : tout chemin de $\beta$-réduction peut rejoindre tout autre chemin, notamment si on arrive à une forme normale ce sera la même) : $\pi_1(\Pi XY) = (\lambda p.p(\lambda xy.x))((\lambda xyf.fxy)XY) \rightarrow ((\lambda xyf.fxy)XY)(\lambda xy.x) \rightarrow \rightarrow (\lambda f.fXY)(\lambda xy.x) \rightarrow (\lambda xy.x)XY \rightarrow \rightarrow X$. Le résultat est le même, \textit{mutatis mutandis}, pour $\pi_2$, à savoir : $\pi_2(\Pi XY) = (\lambda p.p(\lambda xy.y))((\lambda xyf.fxy)XY) \rightarrow ((\lambda xyf.fxy)XY)(\lambda xy.y) \rightarrow \rightarrow (\lambda f.fXY)(\lambda xy.y) \rightarrow (\lambda xy.y)XY \rightarrow \rightarrow Y$. \textbf{(2)} Le couple $(x,y)$ est codé par $\Pi$ en le terme $\Pi xy$ c'est-à-dire (à $\beta$-réduction près) la fonction $\lambda f.fxy$ qui prend une fonction $f$ et l'applique (de façon « currifiée ») aux deux composantes du couple. (Autrement dit, pour appliquer une fonction au couple, on applique la représentation du couple à la fonction !) Pour décoder le couple, il s'agit simplement d'utiliser pour $f$ la fonction $\lambda xy.x$ qui renvoie son premier argument lorsqu'on veut récupérer celui-ci, et c'est ce que fait $\pi_1$, ou la fonction $\lambda xy.x$ qui renvoie son premier argument lorsqu'on veut récupérer celui-ci, et c'est ce que fait $\pi_2$. \textbf{(3)} Voici une implémentation en Scheme, dans laquelle on a pris la liberté d'utiliser des fonctions de plusieurs variables (le Scheme permet de définir des fonctions de plusieurs variables sans passer les arguments un par un de façon « curryfiée » : la notation est \texttt{(f x y)} pour appeler une telle fonction \texttt{f} sur deux arguments \texttt{x} et \texttt{y}, et \texttt{(lambda (x y) ...)} pour en définir une ; par ailleurs, les fonction \texttt{cons}, \texttt{car} et \texttt{cdr} du Scheme sont les fonctions servant nativement à créer et projeter des paires, i.e., ce sont les équivalents natifs des fonctions \texttt{pairing}, \texttt{proj1} et \texttt{proj2} qu'on définit ici) : \noindent\texttt{% (define pairing (lambda (x y) (lambda (f) (f x y))))\\ (define proj1 (lambda (p) (p (lambda (x y) x))))\\ (define proj2 (lambda (p) (p (lambda (x y) y))))\\ (define fromnative (lambda (z) (pairing (car z) (cdr z))))\\ (define tonative (lambda (p) (p cons))) } On peut ensuite faire différents tests, par exemple \texttt{(proj1 (pairing 42 "coucou"))} renvoie \texttt{42}, comme \texttt{(proj1 (fromnative (cons 42 "coucou")))} ; et \texttt{(tonative (pairing 42 "coucou"))} renvoie la paire native, notée \texttt{(42 . "coucou")} en Scheme. Voici maintenant le code équivalent en OCaml : il n'était pas évident \textit{a priori} que le codage puisse être implémenté dans ce langage (i.e., qu'il soit typable), mais il s'avère qu'il l'est, modulo la subtilité qui sera expiquée ci-dessous : \noindent\texttt{% let pairing = fun x -> fun y -> fun f -> f x y\\ let proj1 = fun p -> p (fun x -> fun y -> x)\\ let proj2 = fun p -> p (fun x -> fun y -> y)\\ (* Conversion from and to native pairs *)\\ let fromnative = fun (x,y) -> pairing x y\\ let tonative = fun p -> p (fun x -> fun y -> (x,y))\\ ;; } On peut alors tester que \texttt{proj1 (pairing 42 "coucou")} renvoie \texttt{42}, comme \texttt{proj1 (fromnative (42,"coucou"))} ; et \texttt{tonative (pairing 42 "coucou")} renvoie la paire native, notée \texttt{(42, "coucou")} en OCaml. \textbf{Subtilité :} Même si cette version OCaml fonctionne bien, une petite variation apparemment anodine, à savoir écrire \texttt{let tonative = fun p -> (proj1 p, proj2 p)} (notons que l'équivalent Scheme, \texttt{(define tonative (lambda (p) (cons (proj1 p) (proj2 p))))}, fonctionne parfaitement) pose des problèmes de typage : avec cette nouvelle définition, \texttt{tonative (pairing 42 1729)} fonctionne toujours, mais \texttt{tonative (pairing 42 "coucou")} conduit à une erreur de typage. Sans entrer dans les détails de cette erreur, le problème est que comme le type du résultat de la fonction \texttt{pairing} appliquée à deux types $a$ et $b$ est $(\forall c) (a \to b \to c) \to c$ (par exemple, celui du couple \texttt{pairing 42 "coucou"} est $(\forall c) (\texttt{int} \to \texttt{string} \to c) \to c$), c'est-à-dire une fonction polymorphe acceptant $f : a \to b \to c$ pour n'importe quel type $c$ et renvoyant ce même type $c$ ; la fonction \texttt{tonative} « devrait » donc avoir pour type $(\forall a,b) ((\forall c) ((a \to b \to c) \to c)) \to a \times b$ (ce qui \emph{n'est pas} la même chose que $(\forall a,b,c) ((a \to b \to c) \to c) \to a \times b$), i.e., elle devrait recevoir une fonction polymorphe en argument ; mais le système de typage de OCaml, basé sur l'algorithme de Hindley-Milner, ne peut exprimer que des fonctions polymorphes, pas des fonctions attendant une fonction polymorphe en argument, si bien que OCaml ne peut pas typer correctement la fonction \texttt{tonative} (et selon l'expression précise utilisée, on obtient des approximations plus ou moins bonnes du « vrai » type qu'on vient de dire). Dans un quelconque de ces langages, si on implémente la fonction \texttt{pairing} comme on vient de le dire, la valeur de $\mathtt{x}$ et $\mathtt{y}$ dans $\texttt{pairing}\ \mathtt{x}\ \mathtt{y}$ est stockée dans la \emph{clôture} de la fonction renvoyée, c'est-à-dire les liaisons locales (de $\mathtt{x}$ et $\mathtt{y}$ à leurs valeurs respectives) qui ont été faites lors de la création de la fonction et qui peuvent, ainsi que le montre cet exemple, survivre bien au-delà de la portée de définition de la fonction dans un langage fonctionnel. \end{corrige} % % % \section{Correspondance de Curry-Howard} \exercice\ (${\star}{\star}$)\par\nobreak Pour chacune des preuves suivantes écrites informellement en langage naturel dans le calcul propositionnel, écrire le $\lambda$-terme de preuve (c'est-à-dire le terme du $\lambda$-calcul propositionnel simplement typé étendu d'un type $\bot$ ayant pour type la proposition prouvée) qui lui correspond. Ces raisonnements sont-ils intuitionnistement valables ? Qu'en conclut-on ? \textbf{(a)} On va prouver $\neg\neg(A\Rightarrow B) \Rightarrow \neg\neg A\Rightarrow\neg\neg B$. Pour cela, supposons $\neg\neg(A\Rightarrow B)$ et $\neg\neg A$ et $\neg B$ et on veut arriver à une contradiction. Supposons $A\Rightarrow B$. Alors si on a $A$, on a $B$, ce qui contredit $\neg B$ ; donc $\neg A$ : mais ceci contredit $\neg\neg A$. Donc $\neg(A\Rightarrow B)$. Mais ceci contredit $\neg\neg(A\Rightarrow B)$, comme annoncé. \textbf{(b)} On va prouver $(A\Rightarrow\neg\neg B) \Rightarrow \neg\neg(A\Rightarrow B)$. Supposons $A\Rightarrow\neg\neg B$ ainsi que $\neg(A\Rightarrow B)$ et on veut arriver à une contradiction. Si on a $B$, alors certainement $A\Rightarrow B$, ce qui contredit $\neg(A\Rightarrow B)$ : ceci montre $\neg B$. Si on a $A$, alors notre hypothèse $A\Rightarrow\neg\neg B$ nous donne $\neg\neg B$, d'où une contradiction, et notamment $B$. On a donc prouvé $A\Rightarrow B$, d'où la contradiction recherchée. \textbf{(c)} On va prouver $(\neg\neg A\Rightarrow\neg\neg B) \Rightarrow (A\Rightarrow\neg\neg B)$. Mais on sait que $A$ implique $\neg\neg A$, donc $\neg\neg A \Rightarrow C$ implique $A\Rightarrow C$ (quel que soit $C$, et notamment pour $\neg\neg B$). \begin{corrige} \textbf{(a)} On commence par se placer avec $f_1:\neg\neg(A\Rightarrow B)$ et $x_1:\neg\neg A$ et $k:\neg B$ dans le contexte. Appelons encore $f_0$ l'hypothèse $A\Rightarrow B$. Le raisonnement « si on a $A$, on a $B$, ce qui contredit $\neg B$ » se formalise par le $\lambda$-terme $\lambda(x_0:A). k(f_0 x_0)$ de type $\neg A$ ; le « mais ceci contredit $\neg\neg A$ » s'obtient en lui appliquant $x_1$. Le $\lambda$-terme $\lambda(f_0:A\Rightarrow B).\, x_1(\lambda(x_0:A). k(f_0 x_0))$ est donc de type $\neg(A\Rightarrow B)$, et la contradiction avec $\neg\neg(A\Rightarrow B)$ s'exprime en lui appliquant $f_1$. Finalement, le $\lambda$-terme tout entier (de type $\neg\neg(A\Rightarrow B) \Rightarrow \neg\neg A\Rightarrow\neg\neg B$) est : \[ \lambda(f_1:\neg\neg(A\Rightarrow B)).\, \lambda(x_1:\neg\neg A).\,\lambda(k:\neg B).\, f_1(\lambda(f_0:A\Rightarrow B).\, x_1(\lambda(x_0:A). k(f_0 x_0))) \] (ou en syntaxe Coq : \texttt{fun (f1 : \textasciitilde \textasciitilde(A->B)) (x1 : \textasciitilde\textasciitilde A) (k : \textasciitilde B) => f1 (fun f0 : A -> B => x1 (fun x0 : A => k (f0 x0)))}). \textbf{(b)} On commence par se placer avec $f_1:A\Rightarrow \neg\neg B$ et $k:\neg(A\Rightarrow B)$ dans le contexte. Appelons $y$ l'hypothèse $B$ : alors $\lambda(z:A).y$ est de type $A\Rightarrow B$, donc $k(\lambda(z:A).y)$ est de type $\bot$, ainsi $\lambda(y:B).k(\lambda(z:A).y)$ est de type $\neg B$. Appelons $x$ l'hypothèse $A$ : alors $f_1 x$ montre $\neg\neg B$, donc en l'appliquant au $\lambda$-terme $\lambda(y:B).k(\lambda(z:A).y)$ précédemment trouvé on trouve une contradiction, et $\texttt{exfalso}^{(B)}(f_1 x \, \lambda(y:B).k(\lambda(z:A).y))$ est de type $B$. En abstrayant $x$ dans ce terme on a un terme de type $A\Rightarrow B$, et en lui appliquant $k$ on a la contradiction recherchée. Finalement, le $\lambda$-terme tout entier (de type $(A\Rightarrow\neg\neg B) \Rightarrow \neg\neg(A\Rightarrow B)$) est : \[ \lambda(f_1:A\Rightarrow \neg\neg B).\, \lambda(k:\neg(A\Rightarrow B)).\, k(\lambda(x:A).\,\texttt{exfalso}^{(B)}(f_1 x \, \lambda(y:B).k(\lambda(z:A).y))) \] (ou en syntaxe Coq : \texttt{fun (f1 : A -> \textasciitilde \textasciitilde B) (k : \textasciitilde (A->B)) => k (fun x : A => False\_ind B (f1 x (fun y : B => k (fun z : A => y))))}). \textbf{(c)} La preuve de $A \Rightarrow \neg\neg A$ s'écrit $\lambda(x:A).\lambda(k:\neg A).kx$. La preuve de $A\Rightarrow C$ à partir de $\neg\neg A \Rightarrow C$ s'obtient en composant avec cette fonction, donc finalement le $\lambda$-terme tout entier (de type $(\neg\neg A\Rightarrow\neg\neg B) \Rightarrow (A\Rightarrow\neg\neg B)$) est : \[ \lambda(f_1:\neg\neg A\Rightarrow \neg\neg B).\, \lambda(x:A).f_1(\lambda(k:\neg A).kx) \] (ou en syntaxe Coq : \texttt{fun (f1 : \textasciitilde\textasciitilde A -> \textasciitilde\textasciitilde B) (x : A) => f1 (fun k : \textasciitilde A => k x)}). Les trois raisonnements sont parfaitement valables intuitionnistement (malgré les nombreux « supposons (...), contradiction », il s'agit à chaque fois de \emph{preuves de négation} et pas de \emph{preuves par l'absurde}) : le fait qu'on ait trouvé des $\lambda$-termes (sans aucun call/cc dedans) de ces types le montre. On peut retenir la conclusion que $\neg\neg(A\Rightarrow B)$, $\neg\neg A\Rightarrow\neg\neg B$ et $A\Rightarrow\neg\neg B$ sont tous les trois équivalents (en logique intuitionniste). \end{corrige} % % % \end{document}