\documentclass[a4paper]{article}
\usepackage{entete}
\author{Référence~: Logique mathématique, tome 2. \\René \textsc{Cori}, Daniel \textsc{Lascar}.}
\title{La fonction d'Ackermann}
\date{2011-2012}

\begin{document}
\maketitle

{\em Historique~: } Wilhem Ackermann, alors élève de Hilbert, proposa en 1928 un exemple de fonction récursive, non récursive primitive, à trois variables~:
$$A(m,n,p) = m \to n \to p = m \uparrow^p n.$$

C'est en fait une fonction semblable, mais à seulement deux variables, proposée par R\'ozsa Péter qu'on appelle aujourd'hui {\em fonction d'Ackermann}.


\begin{defi}
    On définit la {\em fonction d'Ackermann} $\xi$ ainsi~:
    \begin{itemize}
        \item Pour tout entier $x$, $\xi(0,x) = 2^x$.
        \item Pour tout entier $y$, $\xi(y,0) = 1$.
        \item Pour tous entiers $x$ et $y$, $\xi(y+1,x+1) = \xi(y,\xi(y+1,x))$.
    \end{itemize}
    Pour chaque entier $n$, on note $\xi_n$ la fonction $x\mapsto \xi(n,x)$, et on a alors~:
    $$\left\{
    \begin{array}{l}
        \xi_0(x) = 2^x \\
        \xi_n(0) = 1 \\
        \xi_n(x+1) = \xi_{n-1}(\xi_n(x))
    \end{array}
    \right.$$
\end{defi}

On voit avec la définition récursive des $\xi_n$ que pour tout entier $n$, la fonction $\xi_n$ est primitive récursive (par procédé de récurrence, sur $n$).

En revanche, cela n'implique pas que $\xi$ est primitive récursive, et d'ailleurs~:

\begin{thm}
    La fonction d'Ackermann $\xi$ n'est pas primitive récursive.
\end{thm}

\begin{proof}
    On va montrer plein de lemmes techniques pour finalement montrer la fonction $\xi$ domine toutes les fonctions primitives récursives.

    \begin{lem}\label{lem:1}
        Pour tous $n$ et $x$ entiers,
        $$\xi_n(x) > x.$$
    \end{lem}
    \begin{prooflem}
        Montrons-le par récurrence sur $n$.
        
        Soit donc $\phi_n$ la proposition \og{} Pour tout entier $x$, $\xi_n(x) > x$ \fg{}.

        \begin{itemize}
            \item Il est assez clair que $\phi_0$.
            \item Soit $n$ un entier. Supposons $\phi_{n-1}$, et montrons $\phi_n$. Pour cela, faisons une récurrence sur $x$.

            Soit donc $\psi_x$ la proposition \og{} $\xi_n(x) > x$ \fg{}.
            \begin{itemize}
                \item $\psi_0$ est toujours clair.
                \item Soit $x$ un entier. Supposons $\psi_{x-1}$ et montrons $\psi_x$.

                On a par définition $\xi_n(x) = \xi_{n-1}(\xi_n(x-1))$, et donc, par $\phi_{n-1}$ on a $\xi_n(x) > \xi_n(x-1)$, c'est-à-dire $$\xi_n(x) \geqslant \xi_n(x-1)+1.$$

                D'après $\psi_{x-1}$, $\xi_n(x-1) > x-1$, d'où $\psi_x$
            \end{itemize}
            On a donc $\phi_n$.
        \end{itemize}
        Donc, par récurrence, on a le lemme.
    \end{prooflem}

    \begin{lem}
        Pour tout $n$, $\xi_n$ est strictement croissante.
    \end{lem}

    \begin{prooflem}
        $\xi_0 = \lambda x .2^x$, donc $\xi_0$ est croissante.

        Pour $n\geqslant 1$, on a la formule $\xi_n(x+1) = \xi_{n-1}(\xi_n(x))$, et donc par le lemme~\ref{lem:1}, $\xi_n(x+1) > \xi_n(x)$.
    \end{prooflem}

    \begin{lem}
        Pour tout $n\geqslant 1$, pour tout entier $x$, on a~:
        $$\xi_n(x) \geqslant \xi_{n-1}(x).$$
    \end{lem}

    \begin{prooflem}
        Par récurrence sur $x$~:
        \begin{itemize}
            \item Pour $x=0$, ouais.
            \item Pour l'hérédité~:

            On a vu $\xi_n(x) \geqslant x+1$, donc par croissance de $\xi_{n-1}$, on a 
            $$\xi_{n-1}(\xi_n(x)) \geqslant \xi_{n-1}(x+1).$$

            Or par définition, $\xi_{n-1}(\xi_n(x)) = \xi_n(x+1)$, d'où le résultat.
        \end{itemize}
    \end{prooflem}

    \begin{defi}
        On note dans la suite $\xi_n^k$ la fonction $\xi_n$ itérée $k$ fois.
    \end{defi}

    \begin{lem}\label{lem:4}
       Les fonctions $\xi_n^k$ sont strictement croissantes. De plus pour tous entiers $m,n,k,h,x$~:
       \begin{align*}
           \xi_n^k(x) < \xi_n^{k+1}(x) \\
           \xi_n^k(x) \geqslant x \\
           \xi_n^k \circ \xi_n^h = \xi_n^{k+h} \\
           \text{Si }m\leqslant n,~\xi_m^k(x) \leqslant \xi_n^k(x)
       \end{align*}
    \end{lem}

    \begin{prooflem}
        C'est facile par récurrence.
    \end{prooflem}

    \begin{defi}
        Soient $f~:~\N\to\N$ strictement croissante, et $g~:~\N^p \to \N$. 

        On dit que $f$ {\em domine} $g$ si pour tout $(x_1,\ldots,x_p)$ sauf un nombre fini, 
        $$g(x_1,\ldots,x_p) \leqslant f(\sup(x_1,\ldots,x_p)).$$

        On pose alors 
        $$C_n=\{g~|~\text{il existe $k$ tel que $g$ soit dominée par $\xi_n^k$}\}.$$
    \end{defi}

    On voit facilement que certaines fonctions sont dans $C_0$~: les projections, les constantes, la fonction successeur, les fonctions $\sup$, l'addition, la multiplication par un entier.

    On remarque aussi que $\xi_n\in C_n$, et si $f,g~:~\N^p \to \N$ telles $f(x_1,\ldots,x_p) \leqslant g(x_1,\ldots,x_p)$ pour tout $(x_1,\ldots x_p)$, alors $g\in C_n$ implique $f\in C_n$.

    Si on montre que $C := \bigcup C_n$ est stable par composition et récurrence, alors $C$ contiendra donc toutes les fonctions primitives récursives.

    \begin{lem}
        Pour tout $n$, $C_n$ est clos par composition.
    \end{lem}

    \begin{prooflem}
       Dans cette preuve, les inégalités seront pour tout uple, sauf un nombre fini.

       Soient $f_1,\ldots,f_m~:~\N^p \to \N$ et $g~:~\N^m \to \N$ des fonctions de $C_n$.

       Montrons que $g(f_1,\ldots,f_m)$ est dans $C_n$ aussi.

       On a l'existence de $k,k_1,\ldots,k_m$ tels que 
       \begin{align*}
           g(y_1,\ldots,y_m) \leqslant \xi_n^k(\sup(y_1,\ldots,y_m)) \\
           f_i(x_1,\ldots,x_p) \leqslant \xi_n^{k_i}(\sup(x_1,\ldots,x_p))
       \end{align*}

       Posons $h=\sup(k_1,\ldots,k_m)$.

       On a alors par le lemme~\ref{lem:4}~:
       $$g(f_1(x_1,\ldots,x_p),\ldots,f_m(x_1,\ldots,x_p)) \leqslant \xi_n^k(\xi_n^h(\sup(x_1,\ldots,x_p))),$$
       d'où le résultat avec le  lemme~\ref{lem:4} à nouveau.
    \end{prooflem}

    \begin{lem}\label{lem:6}
        Pour tous entiers $n,k$ et $x$, on a~:
        $$\xi_n^k(x) \leqslant  \xi_{n+1}(x+k).$$
    \end{lem}

    \begin{prooflem}
        Par récurrence sur $k$.
    \end{prooflem}

    \begin{lem}
        Si $g~:~\N^p\to\N$ et $h~:~\N^{p+2}\to\N$ sont dans $C_n$, alors $f$ définie par récurrence à partir de $g$ et $h$ est dans $C_{n+1}$.
    \end{lem}

    \begin{prooflem}
        Comme dans la preuve précédente, les inégalités seront pour tout uple sauf un nombre fini.

        Les hypothèses sont~:
        \begin{align*}
            g(x_1,\ldots,x_p) \leqslant \xi_n^{k_1}(\sup(x_1,\ldots,x_p)) \\
            h(x_1,\ldots,x_p,y,z) \leqslant \xi_n^{k_2}(\sup(x_1,\ldots,x_p,y,z))
        \end{align*}
        Montrons par récurrence sur $y$ la propriété $\Phi_y=$\og{}$f(x_1,\ldots,x_p,y) \leqslant \xi_n^{k_1+yk_2}(\sup(x_1,\ldots,x_p,y))$\fg{}.
        \begin{itemize}
            \item $\Phi_0$ est évident.
            \item Supposons $\Phi_y$ et montrons $\Phi_{y+1}$.

            On a 
            \begin{align*}
                f(x_1,\ldots,x_p,y+1) & = h(x_1,\ldots,x_p,y,f(x_1,\ldots,x_p,y)) \\
                & \leqslant \xi_n^{k_2}(\sup(x_1,\ldots,x_p,y,f(x_1,\ldots,x_p,y))) \\
                & \leqslant \xi_n^{k_2}(\xi_n^{k_1+yk_2}(\sup(x_1,\ldots,x_p,y)))\text{ par le lemme~\ref{lem:4} et hypothèse de récurrence}
            \end{align*}
            D'où $\Phi_{y+1}$, et donc $\Phi_y$ pour tout $y$.
        \end{itemize}
        En appliquant le lemme~\ref{lem:6}, on a~:
        $$f(x_1,\ldots,x_p,y) \leqslant \xi_{n+1}(\sup(x_1\ldots,x_p,y)+k_1+yk_2).$$


        La fonction $\lambda x_1x_2\cdots x_py.\xi_{n+1}(\sup(x_1,\ldots,x_p,y)+k_1+yk_2)$ est composée de fonctions de $C_{n+1}$, donc est $C_{n+1}$, et donc $f$ aussi.
    \end{prooflem}

    \begin{cor}
        $C$ contient toutes les fonctions récursives primitives.
    \end{cor}

    On peut maintenant montrer que $\xi$ n'est pas primitive récursive.

    Sinon, $\lambda x.\xi(x,2x)$ l'est aussi, donc est dans $C$~:

    $$\text{Il existe }n,k\text{ tels que pour tout $x$ sauf un nombre fini, }\xi(x,2x) \leqslant \xi_n^k(x).$$

    Donc on a $\xi(x,2x) \leqslant \xi_{n+1}(x+k)$ par le lemme~\ref{lem:6}.

    De plus, pour $x$ assez grand~:
    \begin{align*}
        \xi_{n+1}(x+k) & < \xi_{n+1}(2x) \\
        & < \xi_x(2x) \\
        & = \xi(x,2x)
    \end{align*}
    D'où une contradiction.
\end{proof}
\end{document}
