Add an easy computability exercise.

Students tend to confuse being total and being computable, this should help.

1 files changed, 97 insertions, 1 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index f8aa3e5..0bc9ba0 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -85,6 +85,102 @@ Git: \input{vcline.tex}
 \section{Calculabilité}
 
 
+\setcounter{comcnt}{-1}\exercice\ (${\star}$)\par\nobreak
+
+Pour chacune des fonctions partielles suivantes (des entiers naturels
+vers les entiers naturels), dire si elle est totale ou non, calculable
+ou non :
+\begin{itemize}
+\item[(a)] La fonction constante égale à $0$.
+\item[(b)] La fonction valant $0$ en chaque $n\neq 0$ et $1$ en $0$.
+\item[(c)] La fonction valant $0$ en chaque $n\neq 0$ et non définie
+  en $0$.
+\item[(d)] La fonction $n \mapsto A(n,n,n)$, où $(m,n,k) \mapsto
+  A(m,n,k)$ est la fonction d'Ackermann
+  (cf. exercice \ref{exercise-ackermann-indicator-is-p-r} pour sa
+  définition).
+\item[(e)] La fonction $\langle e,x\rangle \mapsto \varphi_e(x)$.
+\item[(f)] La fonction qui à $e$ associe $1$ si
+  $\varphi_e(0)\downarrow$ et $0$ si $\varphi_e(0)\uparrow$.
+\item[(g)] La fonction qui à $e$ associe $1$ si
+  $\varphi_e(0)\downarrow$ et non définie si $\varphi_e(0)\uparrow$.
+\item[(h)] La fonction qui à $e$ associe $0$ si $\varphi_e(0)\uparrow$
+  et non définie si $\varphi_e(0)\downarrow$.
+\end{itemize}
+
+\begin{corrige}
+(a) est totale (définie partout) ; elle est de plus calculable, parce
+  qu'il est évident d'écrire un programme (en gros « \texttt{return
+    0;} ») qui renvoie toujours $0$.  (Avec la définition et
+  numérotation utilisée en cours, on peut d'ailleurs même dire
+  précisément que pour $e = \dbllangle 1,1,0\dblrangle = 23$ la
+  fonction constante égale à $0$ est la fonction $\varphi_e$.)
+
+(b) est totale (définie partout) ; elle est de plus calculable, parce
+  qu'il est évident d'écrire un programme qui teste si son argument
+  vaut $0$, renvoie $1$ si c'est le cas et $0$ sinon (en gros
+  « \texttt{if (n==0) return 1; else return 0;} »).
+
+(c) n'est pas totale puisque sa définition même dit qu'elle n'est pas
+  définie en $0$.  Elle est (partielle) calculable, parce qu'il est
+  évident d'écrire un programme qui teste si son argument vaut $0$,
+  renvoie $0$ si ce n'est pas le cas, et fait une boucle infinie si
+  c'est le cas (en gros « \texttt{if (n!=0) return 0; else while
+    (1);} »).
+
+(d) La fonction d'Ackermann est totale (une récurrence sur $k$, et
+  pour $k$ fixé sur $n$, montre que $A(m,n,k)$ a bien un sens), donc
+  la fonction $n \mapsto A(n,n,n)$ est aussi totale.  De plus, la
+  fonction d'Ackermann est calculable par un algorithme récursif
+  imitant directement sa définition, et on a vu en cours qu'on pouvait
+  utiliser la récursion.  Donc la fonction d'Ackermann et \textit{a
+    fortiori} la fonction $n \mapsto A(n,n,n)$ sont calculables.
+
+(e) La fonction $\langle e,x\rangle \mapsto \varphi_e(x)$ est
+  calculable par l'existence d'un algorithme universel.  Elle n'est
+  pas totale car il existe des $(e,x)$ tels que $\varphi_e(x)\uparrow$
+  (par exemple un programme qui fait une boucle infinie).
+
+(f) La fonction est totale par définition (en tout $e$, elle vaut soit
+  $0$ soit $1$, mais elle est toujours définie).  Il s'agit ici de la
+  fonction indicatrice de $H := \{e \in \mathbb{N} :
+  \varphi_e(0)\downarrow\}$.  Ce $H$ est indécidable par une des
+  variations du problème de l'arrêt (ou par le théorème de Rice),
+  c'est-à-dire justement que sa fonction indicatrice n'est pas
+  calculable.  On a donc affaire à une fonction totale non calculable.
+
+(g) La fonction n'est pas totale car il existe des $e$ tels que
+  $\varphi_e(0)\uparrow$ (par exemple un programme qui fait une boucle
+  infinie).  Elle est (partielle) calculable car il est possible
+  d'écrire un programme qui prend $e$ en entrée, simule l'exécution de
+  $e$ sur l'entrée $0$ (en utilisant la machine universelle, comme
+  en (e)), et renvoie $1$ toujours si l'exécution termine (tandis que
+  si l'exécution ne termine pas, elle n'a, bien sûr, pas d'autre choix
+  que de ne pas terminer).  De façon équivalente, on peut dire que
+  c'est la fonction « semi-indicatrice » du $H$ défini en (f), et ce
+  $H$ est semi-calculable comme variante du problème de l'arrêt.
+
+(h) La fonction n'est pas totale car il existe des $e$ tels que
+  $\varphi_e(0)\downarrow$.  Montrons par l'absurde qu'elle n'est pas
+  calculable : s'il existait $h$ tel que $\varphi_h(e)$ soit la
+  fonction dont on parle (c'est-à-dire $0$ si $\varphi_e(0)\uparrow$
+  et non définie si $\varphi_e(0)\downarrow$), on pourrait décider le
+  problème de l'arrêt de la manière suivante : donné un programme $e$,
+  on lance en parallèle l'exécution de $\varphi_e(0)$ et de
+  $\varphi_h(e)$, et forcément exactement l'un des deux va terminer
+  (si $\varphi_e(0)\downarrow$ c'est qu'elle termine, et si
+  $\varphi_e(0)\uparrow$ c'est que $\varphi_h(e)\downarrow$ par
+  définition), donc on a juste à voir lequel termine ; or on sait que
+  le problème de l'arrêt n'est pas décidable, donc notre hypothèse est
+  absurde (ce $h$ n'existe pas).  De façon équivalente, on peut dire
+  que notre fonction est (à un décalage de $1$ près) la fonction
+  « semi-indicatrice » du complémentaire de $H$ défini en (f), et ce
+  $H$ est semi-calculable non calculable donc son complémentaire n'est
+  pas calculable.
+\end{corrige}
+
+%
+
 \exercice\ (${\star}{\star}$)\par\nobreak
 
 On considère la fonction $f\colon \mathbb{N} \to \mathbb{N}$ qui à $n
@@ -860,7 +956,7 @@ chaque tour de boucle).
 
 %
 
-\exercice\ (${\star}{\star}{\star}{\star}{\star}$)\par\nobreak
+\exercice\label{exercise-ackermann-indicator-is-p-r}\ (${\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}$ :