La fonction d'Ackermann

Martial

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

Cyrano

La récursivité de $A$ est un long exercice commenté dans Cori et Lascar, p.57, exercice 11.

Martial

Merci, @Cyrano. Je viens de voir l'exercice. Effectivement, c'est beaucoup moins trivial que ce que je pensais.

umrk

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 :

• Le numéro atomique du fer, un métal de transition.
• Le nombre de lettres dans l'usage français de l'alphabet latin, si les majuscules ne sont pas distinguées des minuscules et les accents sont ignorés.
• Le nombre de dimensions de l'espace-temps dans la théorie bosonique des cordes, en mécanique quantique.
• C'est souvent le nombre d'épisodes dans les séries de dessins animés japonais.
• Le nombre d'années de mariage des noces de jade.
• Le n° du département français de la Drôme.
• Le numéro de l'autoroute française A26 qui part de l'A5 à la hauteur de Troyes pour atteindre Calais. Elle est appelée l'autoroute des Anglais.
• Le nombre de cantons en Suisse.
• Années historiques : -26, 26, ou 1926.
• La valeur guématrique du Tétragramme YHWH, qui est le nom hébraïque de Dieu.
• En hébreu, le mot "existence" a une valeur numérique de 26. "Amour" vaut 13, et la rencontre de l'amour entre deux personnes vaut donc 2*13 = 26
• Ligne 26 

nicolas.patrois

C’est le nombre de semaines d’une demi-année, sinon on peut demander à un recueil de nombres entiers.

Martial

@umrk : c'est quoi un SGA ?

Thierry Poma

@Martial : bonsoir. J'espère que tu vas bien, ainsi que tes proches. Cela me fait plaisir de te lire.

A mon avis, en fonction de mes humbles connaissances, SGA signifie "Séminaire de Géométrie Algébrique".

Barjovrille

Bonjour, pour un peu plus de détails :

https://fr.wikipedia.org/wiki/Séminaire_de_géométrie_algébrique_du_Bois_Marie

umrk

Tel le Christ, Grothendieck délivrait la parole divine, transcrite par l'apôtre Dieudonné (il est tout à fait remarquable que Dieudonné, à l'époque ponte des mathématiques, Normalien, major de l'agrégation, se soit ainsi mis au service du jeune Grothendieck, dont le seul bagage mathématique, au moment ou il a fait sa connaissance, se résumait à une licence en maths de la fac de Montpellier (bien entendu je ne dénigre pas la fac de Montpellier, où d'ailleurs il a enseigné par la suite). Bel exemple d'humilité ...).

(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).

raoul.S

Amen

Thierry Poma

@Martial : du point de vue métamathématique, voici ce qu'en dit Stephen Cole Kleene dans son Introduction to Metamathematics :

Toutefois, je pense que tu cherches beaucoup plus compliqué.