Développement : La fonction d'Ackermann n'est pas récursive primitive

Détails/Enoncé :

On étudie la fonction de Ackermann, définie sur $\mathbb{N}^2$ par $A_0(m)=m+1$, $A_{n+1}(0)=A_n(1)$ et $A_{n+1}(m+1)=A_n ( A_{n+1}(m) )$.

On montre qu'on peut majorer toute fonction récursive primitive par un fonction $A_n$ définie sur $\mathbb{N}$ (le paramètre $n$ est fixé).

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :

Références utilisées dans les versions de ce développement :

Logique mathématique Tome 2, René Cori, Daniel Lascar (utilisée dans 7 versions au total)
Mathématiques de l'informatique , Dehornoy (utilisée dans 8 versions au total)