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