La fonction d'Ackermann
Bonjour à tous,
J'en arrive pour ainsi dire à la fin de mon aventure. J'ai terminé le chapitre 26 et j'ai complété les annexes 1, 3 et 4. Il me reste l'annexe 2, consacrée à la fonction d'Ackermann. Pour rappel c'est une fonction de $\mathbb{N}^2$ dans $\mathbb{N}$ définie par
$A(0,n)=n+1$.
$A(m+1,0)=A(m,1)$.
$A(m+1,n+1)=A(m,A(m+1,n))$.
Pour des raisons de commodité on définit aussi, pour tout entier $m$, la fonction $A_m : \mathbb{N} \to \mathbb{N}$ par
$A_m(n)=A(m,n)$.
Il est facile de voir que $A_m$ est récursive primitive (dans la suite RP) pour tout entier $m$. Cependant, comme "chacun" sait, $A$ elle-même n'est pas RP. Ça, je pense être en mesure de l'expliquer : j'ai un très bon papier sur le sujet, je peux donner la référence si ça intéresse quelqu'un. Mais mon problème est de démontrer qu'elle est récursive. Intuitivement, ça paraît trivial : on se donne un couple $(m,n)$ d'entiers. Comme $A_m$ est RP, en particulier elle est récursive, donc calculable, par exemple par machines à registres (ou Turing, selon le goût de chacun). Donc, le couple $(m,n)$ étant donné, il suffit d'aller chercher l'algorithme qui calcule $A_m$ et le tour est joué : comme elle est effectivement calculable elle est récursive, et envoir m'sieurs-dames.
Mon problème est : comment formaliser cela sans utiliser la thèse de Church ? Il faudrait un algorithme uniforme. Il me semble me rappeler qu'avec les machines de Turing on peut disposer d'une infinité de rubans, ce qui me rendrait bien service ici : il suffirait de dire à la machine d'aller voir ce qui se passe dans le ruban numéro $m$.
Qu'en pensez-vous ?
Merci d'avance
Martial
Qu'en pensez-vous ?
Merci d'avance
Martial
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Il y a eu 7 SGA (le SGA 4 1/2 ne compte pas ..). Toi c'est 26, moins biblique, mais :
Le nombre 26 est aussi :
-- Schnoebelen, Philippe
(hélas par la suite leurs relations se sont tendues, notamment lorsque Grothendieck est venu saboter, avec sa propagande écologiste radicale (et anti-mathématique !) , le congrès international de mathématiques que Dieudonné organisait à Nice en 1970).