%autotex% Scale: 0.70 %autotex% PoliceSize: 11pt %autotex% Title: Hiérarchie de Grzegorczyk \section{Hiérarchie de Grzegorczyk} Cette note présente la hiérarchie de Grzegorczyk, en commançant par sa définition, quelques propriétés et enfin un théorème qui établit une hiérarchie des fonctions primitives récursives. \subsection{Introduction} La hiérarchie de Grzegorczyk -- du nom du logicien polonais Andrzej Grzegorczyk -- est une hiérarchie de fonctions utilisée en théorie de la calculabilité. % Toutes les fonctions de la hiérarchie de Grzegorczyk sont primitives récursives et toute fonction primitive récursive apparaît dans cette hiérarchie. % Cette hiérarchie classe les fonctions selon leur croissance. Intuitivement, les fonctions d'un niveau croissent moins vite que toutes les fonctions des niveaux supérieurs. \subsection{Définition} \paragraph{Une famille de fonctions} Tout d'abord on introduit un ensemble (infini) de fonctions notées $E_{i}$ pour tout entier naturel $i \geq 0$. % On pose $E_{0}:(x,y)\mapsto x+y$ et $E_{1}:x\mapsto x^{2}+2$. En d'autre terme, $E_{0}$ est la fonction d'addition et $E_{1}$ est une fonction unaire qui élève au carré son argument et ajoute $2$. Ensuite, pour tout entier $n\geqslant 2$, on définit récursivement \[ E_{n}:x \mapsto \begin{cases} 2 & \text{si } x=0\\ E_{n-1}(E_{n}(x-1)) & \text{sinon} \end{cases} \] \paragraph{Quelques valeurs} Voici des exemples de valeurs, calculées avec Python ou OCaml, pour vérifier que ces fonctions sont ``fortement croissantes''. \begin{table}[ht] \begin{footnotesize} \centering \begin{tabular}{c|cccccc} $n$ \textbackslash $x$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ \\ \hline $1$ & $3$ & $6$ & $11$ & $18$ & $27$ & $38$ \\ $2$ & $6$ & $38$ & $1446$ & $2090918$ & $4371938082726$ & $19113842599189892819591078$ \\ $3$ & $38$ & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} \\ $4$ & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} & \textcolor{red}{trop grand} \end{tabular} \caption{Quelques valeurs de $E_n(x)$.} \end{footnotesize} \end{table} En OCaml, une exception \texttt{Stack overflow during evaluation (looping recursion?).} est déclenchée pour les valeurs trop grandes, et en Python le calcul prend juste trop de temps pour être raisonnable (plus d'une heure). Notez qu'il y a une différence dans les résultats donnés par les deux implémentations présentées plus bas. Par exemple, $E_2(6) = 19113842599189892819591078$ calculé en Python (qui utilise des entiers en précisions arbitraires), mais $-926155691629764698$ en OCaml (qui utilise des entiers sur $64$ bits). Dès que le résultat est négatif, cela signifie que OCaml a calculé un entier plus grand que $2^{62}-1$, et donc le calcul devient faux. \paragraph{Code OCaml} Voici un code OCaml qui implémente cette fonction (qui considère que $n>0$) : % \begin{lstlisting}[language=Caml] \begin{verbatim} let rec base_grzegorczyk n x = if n = 1 then x*x + 2 else begin if x = 0 then 2 else base_grzegorczyk (n-1) (base_grzegorczyk n (x - 1)) end ;; (* val base_grzegorczyk : int -> int -> int = *) \end{verbatim} % \end{lstlisting} \paragraph{Code Python} Voici un code Python qui implémente cette fonction : % \begin{lstlisting}[language=Python] \begin{verbatim} def base_grzegorczyk(n, x): if n == 1: return x*x + 2 elif x == 0: return 2 else: return base_grzegorczyk(n-1, base_grzegorczyk(n, x - 1)) \end{verbatim} % \end{lstlisting} \paragraph{Propriétés de croissance} De même que lorsqu'on étudie la fonction d'Ackermann, on peut énoncer les propriétés de croissance suivantes [Gakwaya 1997]. \begin{lemma}\label{lem:1} Pour tout $n$ et $x$, on a : \begin{enumerate} \item $x+1 \leq E_n(x)$, \item $E_n(x) \leq E_{n+1}(x)$, \item $E_n(x) \leq E_n(x+1)$, \item $\forall m \geq 0, (E_n(x))^m \leq E_{n+1}(x+m)$. \end{enumerate} \end{lemma} \paragraph{Hiérarchie} On peut alors définit la hiérarchie de Grzegorczyk : $\mathcal{E}^{n}$ la $n$-ième classe (ou niveau) de la hiérarchie de Grzegorczyk est le plus petit ensemble qui contient : \begin{itemize} \item les fonctions $E_{k}$ pour $k