diff options
Diffstat (limited to 'exercices-inf110.tex')
| -rw-r--r-- | exercices-inf110.tex | 263 |
1 files changed, 250 insertions, 13 deletions
diff --git a/exercices-inf110.tex b/exercices-inf110.tex index 26840c0..10149c1 100644 --- a/exercices-inf110.tex +++ b/exercices-inf110.tex @@ -71,7 +71,7 @@ Git: \input{vcline.tex} \section{Calculabilité} -\exercice\ ($\star$) +\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 @@ -102,7 +102,25 @@ calculable. Mieux : comme la boucle utilisée est bornée \textit{a % -\exercice\label{exercice-image-calculable-est-semi-decidable}\ ($\star$) +\exercice\ (${\star}$) + +Supposons que $A \subseteq B \subseteq \mathbb{N}$. \textbf{(1)} Si +$B$ est décidable, peut-on conclure que $A$ est décidable ? +\textbf{(2)} Si $A$ est décidable, peut-on conclure que $B$ est +décidable ? + +\begin{corrige} +La réponse est non dans les deux cas : pour le voir appelons $H := \{e +\in \mathbb{N} : \varphi_e(0)\downarrow\}$ (disons) : il est +indécidable par une des variations du problème de l'arrêt (ou par le +théorème de Rice). Le fait que $H \subseteq \mathbb{N}$ avec +$\mathbb{N}$ décidable réfute (1), et le fait que $\varnothing +\subseteq H$ avec $\varnothing$ décidable réfute (2). +\end{corrige} + +% + +\exercice\label{exercice-image-calculable-est-semi-decidable}\ (${\star}$) \textbf{(1)} Soit $f\colon \mathbb{N} \to \mathbb{N}$ totale calculable. Montrer que l'image $f(\mathbb{N})$ (c'est-à-dire $\{f(i) @@ -135,7 +153,27 @@ boucle potentiellement infinie comme une boucle pour $i$ allant de $0$ % -\exercice\label{exercice-image-fonction-partielle-calculable}\ ($\star\star$) +\exercice\ (${\star}$) + +Montrer que l'ensemble des $e\in \mathbb{N}$ tels que +$\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$ (rappel : ceci signifie que +\emph{soit} $\varphi^{(1)}_e(0) \downarrow$ et $\varphi^{(1)}_e(1) +\downarrow$ et $\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$, \emph{soit} +$\varphi^{(1)}_e(0) \uparrow$ et $\varphi^{(1)}_e(1) \uparrow$) n'est +pas décidable. + +\begin{corrige} +L'ensemble $F$ des fonctions partielles calculables $f\colon +\mathbb{N} \dasharrow \mathbb{N}$ telles que $f(0) = f(1)$ n'est ni +vide (la fonction totale constante de valeur $0$ est dans $F$) ni +plein (la fonction totale identité n'est pas dans $F$). D'après le +théorème de Rice, l'ensemble des $e$ tels que $\varphi^{(1)}_e \in F$ +est indécidable : c'est exactement ce qui était demandé. +\end{corrige} + +% + +\exercice\label{exercice-image-fonction-partielle-calculable}\ (${\star}{\star}$) \textbf{(1)} Soit $B \subseteq \mathbb{N}$ semi-décidable et non-vide. Montrer qu'il existe $f\colon \mathbb{N} \to \mathbb{N}$ totale @@ -214,7 +252,7 @@ grand on va finir par tester le couple $(n,i)$.) % -\exercice\ ($\star\star$) +\exercice\label{exercice-graphe-calculable}\ (${\star}{\star}$) Soit $f\colon \mathbb{N} \to \mathbb{N}$ une fonction totale : montrer qu'il y a équivalence entre les affirmations suivantes : @@ -296,12 +334,70 @@ tester le couple $(n,q)$.) % -\exercice\ ($\star\star\star$) +\exercice\label{exercice-reconnaitre-fonctions-p-r}\ (${\star}{\star}$) + +Si $e \mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions +primitives récursives en une variable (= d'arité $1$) et $e \mapsto +\varphi^{(1)}_e$ celle des fonctions générales récursives en une +variable, on considère les ensembles +\[ +M := \{e \in \mathbb{N} : \psi^{(1)}_e\text{~définie}\} +\] +\[ +N := \{e \in \mathbb{N} : \exists +e'\in\mathbb{N}.(\psi^{(1)}_{e'}\text{~définie~et~}\varphi^{(1)}_e = +\psi^{(1)}_{e'})\} +\] +Expliquer informellement ce que signifient ces deux ensembles (en +insistant sur le rapport entre eux), dire s'il y a une inclusion de +l'un dans l'autre, et dire si l'un ou l'autre est décidable. + +\begin{corrige} +L'ensemble $M$ est l'ensemble des codes valables de fonction +primitives récursives, c'est-à-dire de codes légitimes dans le langage +primitif récursif ; l'ensemble $N$ qui est $\{e \in \mathbb{N} : +\varphi^{(1)}_e \text{~est~p.r.}\}$ est l'ensemble des codes de +fonctions générales récursives qui s'avèrent être primitives +récursives (même si ce n'est pas forcément manifeste sur le +programme). Si on préfère, $M$ est l'ensemble des \emph{intentions} +primitives récursives, alors que $N$ est l'ensemble des intentions +dont l'\emph{extension} est primitive récursive ; \textit{grosso + modo}, l'appartenance à $M$ se lit sur le code de la fonction, celle +à $N$ se lit sur les valeurs de la fonction. + +Manifestement, $M \subseteq N$, car si $\psi^{(1)}_e$ est définie, on +a $\varphi^{(1)}_e = \psi^{(1)}_e$ (la définition des fonctions +générales récursives \emph{étend} celle des fonctions p.r.). +L'inclusion dans l'autre sens ne vaut pas : on peut calculer la +fonction constante nulle en faisant une boucle infinie, ce qui fournit +un code $e$ tel que $\varphi^{(1)}_e$ est primitive récursive (donc +$e\in N$) et pourtant $\psi^{(1)}_e$ n'est pas définie (donc $e\not\in +M$). + +L'ensemble $M$ est décidable : on peut décider de façon algorithmique +si $e$ est un numéro valable de fonction primitive récursive (i.e., si +$\psi^{(1)}_e$ est définie), il s'agit pour cela simplement de +« décoder » $e$ et de vérifier qu'il suit les conventions utilisées +pour numéroter les fonctions primitives récursives (pour être très +précis, le décodage termine parce que le code d'une liste est +supérieur à tout élément de cette liste). + +L'ensemble $N$ n'est pas décidable : si $F$ désigne l'ensemble des +fonctions p.r. $\mathbb{N} \to \mathbb{N}$ (c'est-à-dire l'image de +$M$ par $e \mapsto \psi^{(1)}_e$), alors $N$ est $\{e\in\mathbb{N} : +\varphi^{(1)}_e \in F\}$, et comme $F$ n'est ni vide ni l'ensemble de +toutes les fonctions générales récursives, le théorème de Rice dit +exactement que $N$ est indécidable. +\end{corrige} + +% + +\exercice\label{exercice-diagonalisation-0-1-fonctions-p-r}\ (${\star}{\star}{\star}$) On considère la fonction $f\colon \mathbb{N}^2 \to \mathbb{N}$ qui à $(e,x)$ associe $1$ si $\psi^{(1)}_e(x) = 0$ et $0$ sinon (y compris -si $\psi^{(1)}_e$ n'est pas définie), où $e \mapsto \psi^{(1)}$ est la -numérotation standard des fonctions primitives récursives en une +si $\psi^{(1)}_e$ n'est pas définie), où $e \mapsto \psi^{(1)}_e$ est +la numérotation standard des fonctions primitives récursives en une variable (= d'arité $1$). La fonction $f$ est-elle calculable ? Est-elle primitive récursive ? @@ -313,12 +409,12 @@ dans $f$ ? 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) ; + 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 @@ -341,6 +437,147 @@ l'autre l'est), mais la démonstration ne se serait pas appliquée telle quelle. \end{corrige} +% + +\exercice\ (${\star}{\star}{\star}$) + +Soit +\[ +Z := \{e \in \mathbb{N} : \exists n \in \mathbb{N}.\, (\psi^{(1)}_e(n) = 0)\} +\] +l'ensemble des codes $e$ des fonctions p.r. $\mathbb{N} \to +\mathbb{N}$ qui prennent (au moins une fois) la valeur $0$ (ici, $e +\mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions +primitives récursives en une variable). + +Montrer que $Z$ est semi-décidable. Montrer qu'il n'est pas +décidable. + +\begin{corrige} +Comme dans le début du corrigé de +l'exercice \ref{exercice-diagonalisation-0-1-fonctions-p-r}, on +explique qu'on peut décider si $\psi^{(1)}_e(n)\downarrow$ (il s'agit +juste de vérifier si $e$ est un code valable de fonction p.r.) et, une +fois ce point vérifié, si $\psi^{(1)}_e(n) = 0$ (on peut calculer +$\psi^{(1)}_e(n) = \varphi^{(1)}_e(n)$ par universalité des fonctions +générales récursives). + +Dès lors, pour semi-décider si $e \in Z$, il suffit de faire une +boucle infinie pour $n$ parcourant les entiers naturels, décider si +$\psi^{(1)}_e(n) = 0$ pour chacun, et si l'un d'eux est effectivement +nul, terminer et renvoyer « oui », sinon on continue la boucle. Ceci +montre que $Z$ est semi-décidable. + +Montrons qu'il n'est pas décidable : pour cela, on va ramener le +problème de l'arrêt à $Z$. C'est en fait essentiellement ce que fait +le théorème de la forme normale de Kleene : en effet, considérons +$(p,x)$ dont il s'agit de décider si $\varphi^{(1)}_p(x)\downarrow$ : +d'après le théorème de la forme normale, ceci se produit si et +seulement si il existe un (entier codant un) arbre de calcul $n$ +attestant que $\varphi^{(1)}_p(x)\downarrow$, ce qu'on écrit +$T(n,p,\dbllangle x\dblrangle)$, où $T$ est un prédicat p.r., +c'est-à-dire qu'il s'écrit $t(n,p,\dbllangle x\dblrangle) = 0$ pour +une certaine fonction p.r. $t$ (qui teste si $n$ code un arbre de +calcul valable pour $\varphi^{(1)}_p(x)$ et renvoie $0$ si c'est le +cas, $1$ sinon). On a ainsi $\varphi^{(1)}_p(x)\downarrow$ ssi +$\exists n\in\mathbb{N}.\, (t(n,p,\dbllangle x\dblrangle) = 0)$. +Maintenant, d'après le théorème s-m-n, on peut calculer de façon +p.r. en $p$ et $x$ le code $\rho(p,x)$ d'une fonction p.r. telle que +$\psi^{(1)}_{\rho(p,x)}(n) = t(n,p,\dbllangle x\dblrangle)$, et +d'après ce qui a été dit juste avant, on a $\rho(p,x) \in Z$, +c'est-à-dire $\exists n\in\mathbb{N}.\, (t(n,p,\dbllangle x\dblrangle) += 0)$, se produit si et seulement si $\varphi^{(1)}_p(x)\downarrow$, +c'est-à-dire $(p,x) \in \mathscr{H}$ (où $\mathscr{H} := \{(p,x) \in +\mathbb{N}^2 : \varphi^{(1)}_p(x)\downarrow\}$ désigne le problème de +l'arrêt). Ceci constitue une réduction \textit{many-to-one} de +$\mathscr{H}$ à $Z$, donc $Z$ ne peut pas être décidable : en effet, +si $Z$ était décidable, pour tester si $(p,x) \in \mathscr{H}$ il +suffirait de tester si $\rho(p,x) \in Z$, donc le problème de l'arrêt +serait décidable, ce qui n'est pas le cas. + +(De nouveau, si on n'aime pas le théorème de la forme normale de +Kleene, on peut faire ça avec des étapes de machine de Turing : +appeler $t(n,p,x)$ la fonction qui renvoie $0$ si la machine de Turing +codée par $p$ termine en $\leq n$ étapes à partir de la configuration +initiale codée par $x$, et $1$ sinon : le reste du raisonnement est +essentiellement identique.) +\end{corrige} + +% + +%% \exercice\ (${\star}$) + +%% Montrer qu'il existe une machine de Turing qui, quand on la lance sur +%% la configuration vierge (c'est-à-dire un ruban vierge et dans +%% l'état $1$), termine après avoir écrit son propre programme sur sa +%% bande\footnote{Par exemple avec la convention suivante : les +%% instructions du programme $\delta \colon \{1,\ldots,m\} \times \{0,1\} +%% \to \{0,\ldots,m\} \times \{0,1\} \times \{\texttt{L},\texttt{R}\}$ +%% sont écrites de la gauche vers la droite dans l'ordre $\delta(1,0)$, +%% $\delta(1,1)$, $\delta(2,0)$, $\delta(2,1)$, etc., chacune étant +%% écrite sous forme du nouvel état, du nouveau symbole, et de la +%% direction codée par $\texttt{L}\mapsto 0, \texttt{R}\mapsto 1$, tous +%% les trois en unaire séparés par des $0$.} + +% + +\exercice\ (${\star}{\star}$) + +Soit $f \colon\mathbb{N} \to \mathbb{N}$ une fonction calculable par +une machine de Turing en \emph{complexité d'espace} primitive +récursive : cela signifie qu'il existe $p \colon\mathbb{N} \to +\mathbb{N}$ primitive récursive et une machine de Turing $\mathscr{M}$ +telle que si on lui présente $n \in \mathbb{N}$ en entrée (écrit avec +les conventions usuelles, c'est-à-dire en unaire sur la bande), la +machine s'arrête en temps fini en ayant écrit $f(n)$ sur la bande, et +de plus le nombre de cases de la bande que la tête de lecture a +parcourues est $\leq p(n)$ (c'est-à-dire que $\mathscr{M}$ a utilisé +$\leq p(n)$ cellules mémoire pour faire le calcul). + +On veut montrer que $f$ elle-même est primitive récursive +(c'est-à-dire qu'une fonction calculable en complexité d'espace +p.r. est elle-même p.r., de la même manière qu'une fonction calculable +en complexité en temps p.r. est elle-même p.r.). + +\textbf{(1)} Si $\mathscr{M}$ a $\leq m$ états, montrer que le calcul +de $f(n)$ par $\mathscr{M}$ ne peut faire intervenir qu'au plus +$m\times p(n)\times 2^{p(n)+n}$ configurations différentes (on rappelle +qu'une \emph{configuration} est la donnée d'un état, d'une position de +la tête, et de la valeur de chaque cellule du ruban). + +\textbf{(2)} En déduire que le calcul de $f(n)$ par $\mathscr{M}$ +termine en au plus $m\times p(n)\times 2^{p(n)+n}$ étapes +(\textit{indication :} sinon le calcul bouclerait indéfiniment, et on +a supposé que ce n'était pas le cas). + +\textbf{(3)} En déduire que $f$ est primitive récursive. + +\begin{corrige} +\textbf{(1)} Une configuration de l'exécution de $\mathscr{M}$ est la +donnée d'un état parmi au plus $m$, d'une position de la tête parmi au +plus $p(n)$ (puisque la tête visite au plus ce nombre de cellules), et +de la valeur de chaque cellule du ruban ; or au plus $p(n)+n$ cellules +peuvent contenir un $1$ (à n'importe quel moment de l'exécution), car +la tête n'en viiste qu'au plus $p(n)$ et au plus $n$ portent un $1$ +initialement : il y a donc au plus $2^{p(n)+n}$ configurations +possibles du ruban, et au plus $m\times p(n)\times 2^{p(n)+n}$ +configurations de l'ensemble de la machine. + +\textbf{(2)} Si $\mathscr{M}$ retombe sur une configuration exacte +qu'elle a déjà exécutée, elle exécutera de nouveau exactement les +mêmes instructions et ne retombera indéfiniment sur cette +configuration sans jamais finir. Comme on a supposé que le calcul +terminait, c'est qu'il doit parcourir des configurations toutes +distinctes, donc termine en au plus $m\times p(n)\times 2^{p(n)+n}$ +étapes. + +\textbf{(3)} On vient de montrer que le calcul de $f$ par +$\mathscr{M}$ es fait en temps au plus $m\times p(n)\times +2^{p(n)+n}$. Mais ceci est une fonction p.r. de $n$ (car $p$ l'est, +et que $k \mapsto 2^k$ l'est, et que $m$ est une constante ici). Donc +$f$ est calculée en complexité en temps p.r., donc elle est elle-même +p.r. +\end{corrige} |