Discussion:Fonction d'Ackermann

Il serait bon que nous réussissions à faire de cet artcle un article de qualité Stendhalconques 16 février 2007 à 10:50 (CET)

Parfaitement d'accord ! Les Wikipédia anglophone, germanophone et espagnophone y sont arrivées ; alors, pourquoi pas nous ? Ekto - Plastor 20 février 2007 à 19:35 (CET)

Grands systèmes

Quelqu'un sait-il ce que sont les "grands systèmes informatiques" dont il est question? Cette notion est-elle d'actualité? Merci :) Ripounet (d) 23 février 2009 à 16:17 (CET)

Moi je m'interroge sur l'utilité évoquée dans la rubrique Applications pratiques. Que l'on se serve de cette fonction comme exemple type à essayer ok, mais sa vraie utilité est théorique il me semble. En tant qu'exemple de fonction récursive, mais pas récursive primitive. --OPi (d) 28 mars 2009 à 14:39 (CET)

idem, je me demande pourquoi "Cette fonction prend toute son utilité dans le langage de programmation Haskell, langage très efficace dans le traitement des fonctions récursives.". La section "application" semble fumeuse. --129.88.133.122 (d) 26 janvier 2010 à 11:47 (CET)

C'est n'importe quoi. Plus précisément: "utilité dans les benchmark", il s'agit d'une fonction qui croît très vite, et qui est donc très lente à calculer; elle peut être utilisée comme micro-benchmark pour tester le support de la récursion dans une implémentation d'un langage, mais en pratique (pour une raison que j'ignore, sans doute l'habitude) la fonction Tak (nommée en l'honneur de Takeuchi). Je doute que ça constitue réellement une "application pratique", ou alors il faudrait considérer par exemple que la notion de "Palindrome" a pour application pratique le fait de fournir un exercice ultra-classique pour les apprentis programmeurs... Bref, je comprends comment ça s'est trouvé là, mais la forme actuelle ne va pas du tout. Pour la phrase derrière sur le langage "Haskell", c'est encore pire; encore une fois il est effectivement facile d'écrire Ackermann en Haskell (ou dans tout langage fonctionnel correct), mais dire qu'elle "prend toute son utilité" en Haskell, ça n'a pas de sens et ça décrédibilise l'article. Je vais essayer de modifier l'article pour reformuler cette partie en retirant la référence à Haskell et en reformulant la première phrase. Bluestorm (d) 3 juillet 2011 à 12:50 (CEST)

Implémentation

à force de faire du ménage dans les implémentations, il n'en restait plus qu'une ...

Il y a peut-être une juste mesure à trouver entre trop et pas assez.

Je propose ici 3 implems :

• l'implémentation initiale,
• une implémentation caml (tres fonctionnelle),
• une implémentation prolog (où l'on voit peut-être mieux la raison de l'explosion)

On peut en rajouter d'autres si elles sont significativement différentes...

--129.88.133.122 (d) 26 janvier 2010 à 13:08 (CET)

Importance épistémologique

C'est aussi à propos de l'article Thèse_de_Church et Fonction_récursive_primitive.

Constat : Il n'y a pas dans l'article Fonction_d'Ackermann ou dans les articles cités précédemment, de liens croisés, mettant en perspective l'étendue de la thèse de Church, mais la limitation à certains systèmes tout de même assez riches, parmi lesquels il n'y a pas les fonctions récursives primitives, la preuve étant apportée par la fonction d'Ackermann.

Bémol : il y a une phrase mystérieuse (fait-elle un lien ?) :

La croissance exponentielle des problèmes liés aux grands systèmes informatiques est en relation également avec la thèse de Church.

et j'aimerais que l'on me l'explique (sinon, est-ce que l'on peut la supprimer ?)

Peut-on transformer la section "Fonction récursive, mais pas récursive primitive" en "Importance épistémologique" pour parler de la fonction d'Ackermann comme fonction récursive, mais pas récursive primitive (ce qui est fait pour le moment, et ce pourquoi elle est surtout connue) et prolonger/ajouter en fin pour parler de la thèse de Church :

Par suite, l'exemple de la fonction d'Ackermann, montre que la notion de calculabilité introduite par les Fonction_récursive_primitive n'est pas la notion de calculabilité la plus générale, celle atteinte avec un grand succès par la Thèse_de_Church. En effet, la fonction d'Ackermann est calculable au sens de Turing et de Church, mais pas à l'aide de Fonction_récursive_primitive. C'est l'exemple qui montre que la Thèse_de_Church ne concerne pas tous les systèmes de calcul. Il existe des systèmes de calculs, qui semblent pourtant généralistes et puissants comme les Fonction_récursive_primitive, qui ne sont pas équivalents aux machines de Turing et au Lambda-calcul. La calculabilité de la Fonction_d'Ackermann sert ici de critère distinctif.

--Bdenis (d) 18 juin 2011 à 12:28 (CEST)

L'équivalent des machines de Turing et du calcul lambda n'est-ce pas les fonctions récursives plutôt que les fonctions récursives primitives... --OPi (d) 21 juin 2011 à 11:05 (CEST)

Je ne suis pas d'accord avec le contenu de ce paragraphe :

• il est évident qu'il y a des systèmes de calcul qui sont moins généraux que les machines de Turing, la thèse de Church dit juste que l'on ne peut aller au delà des fonctions calculables par les machines de Turing
• une fois que l'on connait un peu de calculabilité, il est (aujourd'hui que l'on a mieux compris) assez immédiat par diagonalisation que des systèmes formels comme les définitions primitives récursives, on peut ajouter les récurrences doubles, etc. ne peuvent engendrer toutes les fonctions calculables (la fonction d'évaluation des ces définitions ne peut être calculable dans le même système). La fonction d'Ackermmann a joué un rôle historique, l'avantage de s'écrire facilement (et suit en fait la même idée) mais l'"importance épistémologique" ne me semble pas évidente, à sourcer pour le moins. Proz (d) 28 juin 2011 à 01:21 (CEST)

Application patique

Il n'est pas vrai que la fonction d'Ackermann permet de tester les implantations des langages de programmation. Elle croit trop vite pour cela. Si le programme sature sa mémoire, ça n'est pas dû à la mauvaise implantation, mais à la complexité intrinsèque de la fonction. Cela n'est pas le cas de la fonction de Takeuchi. D'autre part, il y a une confusion entre la fonction d'Ackermann et sa description récursive. Je rappelle que la première implantation de la fonction d'Ackermann a été faite par Rice en 1965 sans récursivité! --Pierre de Lyon (discuter) 28 avril 2017 à 18:54 (CEST)

Théorème probablement faux

La page indique: On montre assez facilement par récurrence que :

$A(m,n)=2\uparrow ^{m-2}(n+3)-3=\phi (2,n+3,m-1)-3$.

Ce résultat, qui semble vrai pour m entre 1 et 3, est faux pour m = 4 et n = 0. En effet, A (4, 0) = 13 tandis que phi(2, 3, 3) = 65536!

Vasywriter (discuter) 16 mars 2019 à 18:49 (CET)

L'article en anglais donne des informations sur cette question dans le tableau de la section Table of values. --Pierre de Lyon (discuter) 16 mars 2019 à 22:34 (CET)

Pour $m=4$ et $n=0$, $A(m,n)=13$, tandis que $\phi (2,n+3,m-1)-3=\phi (2,3,3)-3=65533$. Donc, la relation $A(m,n)=\phi (2,n+3,m-1)-3$ semble ne pas tenir pour tout m et tout n.

$\phi (2,3,3)$ ne se calcule pas facilement à la main, mais on peut obtenir sa valeur par un petit programme, par exemple le programme C ci-dessous. La différence de valeurs dans le cas $m=4$ et $n=0$ a d'ailleurs été mise en évidence par l'utilisation de la plateforme de réécriture REC et confirmée par différents langages/compilateurs, dont Maude, Haskell et LOTOS.

#include <stdio.h>
int phi (int m, int n, int p) {
if (p == 0) return m + n;
if ((n == 0) && (p == 1)) return 0;
if ((n == 0) && (p == 2)) return 1;
if (n == 0) return m;
return phi (m, phi (m, n-1, p), p-1);
}
int main () {
printf ("%d\n", phi (2, 3, 3));
}

Vasywriter (discuter) 19 mars 2019 à 09:52 (CET)

Erreur virée. Mea culpa. Anne, 18 h 42

Ne faudrait-il pas virer également la partie de cette phrase que j'ai souligné « À l'origine, Ackermann considéra une fonction ϕ(m, n, p) dépendant de trois variables, et consistant, si p > 1, à calculer la puissance itérée p – 1 fois de m par n, c'est-à-dire m → n → (p – 1) en notation de Conway.>» car cette définition de ϕ ne correspond pas à la définition par récurrence. Dans la définition par récurrence ϕ(m, n, 3) = m → (n+1) → 2. (Si j'ai bien calculé et si j'en crois WP:en). HB (discuter) 19 mars 2019 à 18:52 (CET)

PS Le tableau du site anglais est faux, la ligne 5 et la ligne 6 sont identiques. HB (discuter) 19 mars 2019 à 18:52 (CET)

Bouts virés. J'ai aussi essayé de coller au plus près du texte d'Ackermann pour sa définition (à relire). Attention l'itération d'Ackermann n'est pas l'itération de Knuth (d'où je crois, la confusion). Ne faudrait-il pas remettre les defs par ordre chronologique : Ackermann d'abord et Péter ensuite ? HB (discuter) 20 mars 2019 à 09:13 (CET)

La définition que l'on utilise actuellement est, de ce que je connais, celle à deux variables, donc je pense qu'il faut la privilégier. Elle sert pour hiérarchiser la complexité des fonctions primitives récursives (vue comme famille de fonctions à une variable). Proz (discuter) 20 mars 2019 à 13:39 (CET)

Fortran

J'imagine que c'est bien connu en 1965 qu'on peut calculer théoriquement toutes les fonctions calculables dans un langage de type Fortran, qui possède un goto, voir en:Register machine. Rice montre comment éviter les appels récursifs dans le calcul de la fonction d'Ackermann, en utilisant un tableau des valeurs successives, et affirme que c'est toujours possible pour une fonction calculable d'après le théorème de forme normale de Kleene. Proz (discuter) 19 juillet 2021 à 20:56 (CEST)