Home / Words / Sequences / Ackermann function

Ackermann Function

Definition of the Ackermann function

The function A : (m, n) |--> A(m, n) of Ackermann defined from N × N by: 

          If m = 0, then A(0, n) = n+1,
          else if n=0, A(m, 0) = A(m-1, 1)
          then A(m, n) = A(m-1, A(m, n-1))


Ackermann function grows very rapidly, especially n |--> A(n, n) grows faster than any polynomial or even exponential function.


Calculation of A(m, n)

fonction d'Ackermann


cherche exemple efface

In Scheme

The program following is written in 'Scheme' can be run with Mit-scheme 
        (define (A m n)
          (cond ((= m 0) (+ n 1))
                ((= n 0 ) (A (- m 1) 1))
                (else (A (- m 1) (A m (- n 1))))))
To start the program: 
        scheme -load ack.s
Exemple de calcul : 
        1 ]=> (A 3 8)

        ;Value: 2045
The formulas given in the following paragraph for m less than or equal to 4, allow a significant time saving in some calculations.
The first lies in the definition, the others are obtained by induction, (see the demo for the first values of m).

Notations

^ of Donald Knuth

The notations ^^ used in expressions below are from Donald Knuth. 

    A(0, n) = n+1,  A(1, n) = n+2,  A(2, n) = 2*n + 3,  A(3, n) = 2^(n+3)-3,
    A(4, n) = 2^2^2^... 2^2^16 -3 = 2^^(n + 3) - 3, A(5, n) = 2^^^(n + 3) - 3
    A(6, n) = 2^^^^(n + 3) - 3 ...

Their definition is a kind of generalization of powers:
m^n = m.m.m...m (n factors) is the usual exponential notation for powers,
m^^n = m^m^m^m...^m=m^(m^(m^(m...^m)...)) is an iterated exponential,
for example A(4, 1)=2^^(1+3) -3 = 2^^4 -3 = 2^2^2^2 -3 = 65536 -3 = 65533
m^^^n=m^^m^^m^^m...^^m
m^^^^n=m^^^m^^^m^^^m...^^^m
and so on, (n is the number of elements m written).


Ackermann Number

John H. Conway notation ‐>

Conway notation is: a --> b --> c = a^^...^^b (with c arrows ^)

Ackermann's function is then written A(m,n)= 2 -> (n+3) -> (m-2) -3


Simples calculations




A(m,n)0 1 2 3 4 5 6 7 8 9 10 11 12 




01 2 3 4 5 6 7 8 9 10 11 12 13




12 3 4 5 6 7 8 9 10 11 12 13 14




23 5 7 9 11 13 15 17 19 21 23 25 27 




35 13 29 61 125 253 509 1021 2045 4093 8189 16381
32765




413
65533
A(4,2)                     




565533                     
 

Calculating A(4, 2) is as follows: 
    A(4, 2) = A(3, A(4, 1)) = A(3, 2^16 -3)) = 2^2^16 -3 = 20035...6733
The result is easily obtained using the software multiprecision bc. One can also determine the number of digits of the result: 19,729 in base ten.
The value is the same than that found by (1) 
    echo 'a=2^(2^16)-3;length(a)'|bc -q
The calculation of A(4,3) = A(3, A(4,2))=A(3, 2^(2^16) -3)=2^(2^(2^16))-3 is beyond the capabilities of bc.

Other definitions

The book "Structure and Interpretation of Computer Programs" by Harold Abelson / Gerald Jay Sussman with Julie Sussman, (InterEditions) gives a different version of the Ackermann function. 
     If n = 0, then B(m, 0) = 0
     else if m = 0, then B(0, n) = 2n
     else if n = 1, then B(m, 1) = 2
     else A(m, n) = B(m-1, B(m, n-1))
One can see that this other function denoted by B and for n>0 we have B(0, n)=2n, B(1, n)=2n, B(2, n)=22n ...
In the book of mathematical logic of R. Cori and D. Lascar one can find the definition 
      i)  for all integers x, E(0, x)=2^x;
      ii) for all integers y, E(y, 0)=1,
      iii) for all integers x et y, E(y+1, x+1)=E(y,E(y+1,x)).
all versions given in this page are simplifications of the function originally built by Ackermann.

Recursion

Ackermann's function is not primitive recursive.

See Volume II of the book by R. Cori et D. Lascar for definitions and for a demonstration.
The set of primitive recursive functions is the set that contains the constant functions, projections and functions and the successor function. This set is closed for definitions by induction and for composition.
Ackermann function (one or the other of the variants above) is not in this set.


Documents, Links


Home / Words / Sequences / Ackermann function

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014