The graph of the Ackermann function is p.r.

1 files changed, 235 insertions, 0 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index 10149c1..59fd82a 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -579,6 +579,241 @@ $f$ est calculée en complexité en temps p.r., donc elle est elle-même
 p.r.
 \end{corrige}
 
+%
+
+\exercice\label{exercice-tableaux-fonctions-p-r}\ (${\star}{\star}$)
+
+On s'intéresse à des tableaux d'entiers naturels, indicés par les
+entiers naturels, dont toutes les valeurs valent $0$ sauf un nombre
+fini (i.e., des fonctions $\tau \colon \mathbb{N} \to \mathbb{N}$ dont
+le support $\{i \in \mathbb{N} : \tau(i) \neq 0\}$ est fini).  Un tel
+tableau $\tau$ sera Gödel-codé comme un entier naturel sous la forme
+(disons) de la liste $\dbllangle \langle i_1,\tau(i_1)\rangle, \ldots,
+\langle i_k,\tau(i_k)\rangle \dblrangle$ où $i_1 < i_2 < \cdots < i_k$
+sont les indices tels que la valeur $\tau(i)$ dans le tableau à cet
+indice soit $\neq 0$.
+
+\textbf{(1)} Sans rentrer dans énormément de détails, expliquer
+pourquoi la fonction $(\tau,i) \mapsto \tau(i)$ (« lecture du tableau
+$\tau$ à l'indice $i$ ») et $(\tau,i,v) \mapsto \tau'$ où $\tau'(j) =
+\tau(j)$ sauf $\tau'(i) = v$ (« modification du tableau $\tau$ à
+l'indice $i$ pour y mettre la valeur $v$ ») sont primitives
+récursives.
+
+\textbf{(2)} Sans rentrer dans énormément de détails, en déduire
+pourquoi, du coup, un algorithme primitif récursif peut utiliser un
+tableau dans une boucle où elle lit et écrit des valeurs arbitraires
+du tableau.
+
+\begin{corrige}
+\textbf{(1)} La fonction de lecture $(\tau,i) \mapsto \tau(i)$
+consiste à parcourir tous les couples de la liste $\dbllangle \langle
+i_1,\tau(i_1)\rangle, \ldots, \langle i_k,\tau(i_k)\rangle \dblrangle$
+qui représente le tableau et, pour chacune, comparer $i$ à la première
+composante et, s'il y a égalité, renvoyer la seconde composante, sinon
+renvoyer $0$.  La boucle est bornée a priori car elle parcourt une
+liste connue (dont la longueur est majorée par le numéro qui la code).
+Comme le décodage des couples (et donc des listes) est primitif
+récursif, tout ceci est primitif récursif.
+
+La fonction d'écriture $(\tau,i,v) \mapsto \tau'$ consiste à parcourir
+la liste qui représente le tableau, et si on a $i = i_r$, modifier la
+seconde composante du couple correspondant, tandis que si on a $i_r <
+i < i_{r+1}$ (ou $i < i_0$ ou $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}$)
+
+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{exercice-tableaux-fonctions-p-r}).
+
+\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{exercice-tableaux-fonctions-p-r}.  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{exercice-graphe-calculable} 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}
 
 
 %