Informatique théorique
Exercice :
La Fonction d’Ackermann : Calcul de A(4,4)
Vu la complexité du calcul, on a procédé à la réalisation d’un programme sur C, dont voici le code :
Donc on constate que le A(4,4) a causé une saturation du système.
Ce phénomène étant tout à fait normal, vu le comportement de la fonction d’Ackermann. Celle-ci croit d’une manière
extrêmement rapide, passant initialement d’une adition, à une multiplication,
ensuite à une exponentiation, et par la suite à une réitération de l’exponentiel,
ainsi de suite :
-
A( m
, 1 ) = 2 + (m+3) – 3 Adition
-
A( m
, 2 ) = 2 * (m+3) – 3 Multiplication
-
A( m
, 3 ) = 2(m+3) – 3 Exponentiation
-
A( m
, 4 ) = (…(2)2)…)2 – 3 Réitération
de l’exponentiel
Alors A(4,4) ne peut être calculée via un
ordinateur simple, du moment que l’unité de calcul (UC) de celui-ci ne peut
supporter le nombre d’opérations que demande le calcul de A(4,4).