Ackermann’s function

I recapitulated the main ideas of Ackermann’s function.

————————-

* Ackermann function

(1) A(1,j) = 2^i for j>=1
(2) A(i,1) = A(i-1,2) for i>=2
(3) A(i,j) = A(i-1, A(i, j-1)) for i,j>=2

ex>

A(2,2) = A(2-1, A(2,2-1))
= A(1, A(2,1))
= 2^A(2,1)

A(2,3) = A(2-1, A(2,3-1))
= A(1, A(2,2))
= 2^A(2,2)

=> If i=2, A(i,j) = 2^A(i-1,j)

A(3,1) = A(3-1,2)
= A(2,2)

A(3,2) = A(3-1, A(3,2-1))
= A(2, A(3,1))
= A(2, A(2,2))
= A(2, 2^2^2)
= A(1, A(2, 2^2^2-1))
= A(1, A(2, 15))
= A(1, 2^2^2^..^2) // ^2가 15개
= 2^2^2^…^2 // ^2가 16개

=> If i=3, A(3,1) = 2^2^2
In case of A(3,j) such that j>=2, sixteen ^2 is appended to 2

* Inverse of ackermann function

alpha(M,N) = min{ i>=1 | A(i, ceil(M/N)) > logN }

* Single variable inverse of ackermann function

log*N is number of times the logarithm of N needs to be applied until N<=1 => alpha(M,N) grows even slower than log*N.

Similar Posts:

Post a Comment

Your email is never published nor shared.