Fonction d'Ackermann en OCaml : implémentation

La fonction d'Ackermann est l'exemple canonique de fonction récursive qui explose : non primitive récursive, ses valeurs grandissent si vite que même $A(4, 2)$ dépasse le nombre d'atomes dans l'univers observable.

Définition

$$A(m, n) = \begin{cases} n + 1 & \text{si } m = 0 \\ A(m-1, 1) & \text{si } m > 0, n = 0 \\ A(m-1, A(m, n-1)) & \text{sinon} \end{cases}$$

Implémentation OCaml

let rec ackermann m n =
  if m = 0 then n + 1
  else if n = 0 then ackermann (m - 1) 1
  else ackermann (m - 1) (ackermann m (n - 1))

Traduction directe de la définition. OCaml étant un langage fonctionnel à évaluation stricte, la récursion termine pour $m, n$ entiers positifs — mais très lentement.

Explosion combinatoire

Dans la pratique, on ne calcule jamais $A(m, n)$ pour $m \ge 4$. L'algorithme sert essentiellement à illustrer la notion de fonction non primitive récursive.

$A(0, n) = n + 1$
$A(1, n) = n + 2$
$A(2, n) = 2n + 3$
$A(3, n) = 2^{n+3} - 3$
$A(4, 2)$ dépasse $10^{19728}$

À retenir

La fonction d'Ackermann est un classique des exercices en théorie de la calculabilité et en analyse de complexité. C'est elle qui apparaît dans l'analyse amortie de l'union-find (la fameuse fonction « inverse d'Ackermann » $\alpha$, qui croît si lentement qu'on la considère quasi-constante).

La croissance extraordinaire

Pour appréhender la vitesse de croissance d'Ackermann :

La fonction $A(m, n)$ est non primitive récursive : elle croît plus vite que toute fonction récursive primitive (fonctions définissables avec boucles for bornées). C'est la raison historique de sa définition par Wilhelm Ackermann en 1928 — produire un contre-exemple à une conjecture de David Hilbert.

$A(4, 0) = 13$
$A(4, 1) = 65533$
$A(4, 2) = 2^{65536} - 3$ (nombre à plus de 19 000 chiffres)
$A(4, 3)$ dépasse tout entendement physique
$A(5, 0) = 65533$ — déjà énorme pour une valeur apparemment simple

Mémoïsation et optimisations

L'implémentation naïve évalue la même sous-expression des milliards de fois. Une mémoïsation peut accélérer le calcul pour $m \le 3$ :

let memo = Hashtbl.create 1000
let rec ackermann m n =
  try Hashtbl.find memo (m, n)
  with Not_found ->
    let r = if m = 0 then n + 1
    else if n = 0 then ackermann (m - 1) 1
    else ackermann (m - 1) (ackermann m (n - 1))
    in Hashtbl.add memo (m, n) r; r

Mais pour $m \ge 4$, même la mémoïsation ne sauve rien : les valeurs sont trop grandes pour tenir en mémoire.

L'inverse d'Ackermann en analyse de complexité

La fonction $\alpha(n)$, « inverse d'Ackermann », est définie de sorte que $\alpha(n)$ croit extrêmement lentement. Pour tout $n \le A(4, 4)$ (nombre astronomique), $\alpha(n) \le 4$.

Elle apparaît dans l'analyse amortie de structures de données comme l'union-find (théorème de Tarjan 1975) : la complexité amortie d'une opération est $O(\alpha(n))$, c'est-à-dire essentiellement constante en pratique.

Une question ou une suggestion ? Écrivez-nous.

Fonction d'Ackermann en OCaml