Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Fonction d'Ackermann
Résumé
Dans la théorie de la récursivité, la fonction d'Ackermann (aussi appelée fonction d'Ackermann-Péter) est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la forme qu'en a proposée la mathématicienne Rózsa Péter, comme une fonction à deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général A(m, n).
Dans les années 1920, Wilhelm Ackermann et Gabriel Sudan, alors étudiants sous la direction de David Hilbert, étudient les fondements de la calculabilité. Sudan est le premier à donner un exemple de fonction récursive mais non récursive primitive, appelée alors fonction de Sudan. Peu après et indépendamment, en 1928, Ackermann publie son propre exemple de fonction récursive mais non récursive primitive. À l'origine, Ackermann considère une fonction φ(m, n, p) dépendant de trois variables.
Ackermann démontre que sa fonction φ est bien récursive, c'est-à-dire une fonction qu'un ordinateur idéalisé peut calculer. Dans Sur l'infini, David Hilbert conjecture que la fonction d'Ackermann n'est pas récursive primitive. Cette conjecture est établie par Ackermann lui-même dans son article « Zum Hilbertschen Aufbau der reellen Zahlen ». Sur l'infini est l'article le plus important de Hilbert sur les fondements des mathématiques, servant de cœur à son programme pour fixer la base des nombres transfinis.
Une fonction de seulement deux variables est donnée plus tard par Rózsa Péter et Raphael Robinson ; c'est cette dernière qui est connue aujourd'hui sous le nom de fonction d'Ackermann.
La fonction d'Ackermann-Péter est définie récursivement comme suit :
Autrement dit :
On montre alors que :
avec (n + 3) deux empilés, noté également en utilisant la notation des puissances itérées de Knuth.
avec (n + 3) deux, également noté .
et plus généralement :
Ackermann a initialement proposé cette fonction à trois paramètres :
Elle satisfait aux égalités suivantes :
et, plus généralement, si est définie par
est la b itérée de en
La seule opération effectuée lors du déroulement de la fonction d'Ackermann est l'ajout de 1 (lorsque m est nul).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.