(Recursively) defined as follows,

A(0,n) = n+1
A(m+1,0) = A(m,1)
A(m+1,n+1) = A(m, A(m+1,n)),
Ackermann's function grows very quickly. In fact,
A(1,n) = A(0, A(0, ..., A(0,n)...)) = 2n
A(2,n) = A(1, A(1, ..., A(1,n)...)) = 2^(n+1)
with each successive step proceeding along the hierarchy addition, multiplication, exponentiation, ...

Ackermann's function is recursive (equivalently, computable), but it is not primitive recursive. In fact, if we define f_k(n) = A(k,n) then for each k, f_k is primitive recursive. It is defined for all inputs; this shows that while every primitive recursive function is a total computable function, the converse is not true.

In Perl, using the Math::BigInt package so it can handle large numbers:

use Math::BigInt;  # mmm... bignums

# Yes, it's a bug that neither input value can be 0. A(0, n) is trivial,
# while A(m, 0) = A(m-1, 1)
($x=shift) && ($y=shift) || die "usage: $0 m n\n";

print Ack($m, $n), "\n";

sub Ack{
    my $m=shift;
    my $n=shift;
    return $n+1 if $m==0;            # Ack(0,n)=n+1
    # If $n==0, then $n+1==1 which is what we want
    return Ack($m-1, $n+1) if $n==0; # Ack(m,0)=Ack(m-1,1)
    return Ack($m-1, Ack($m, $n-1)); # Ack(m,n)=Ack(m-1, Ack(m, n-1))

However, A(1, n) = A(0, A(1n-1)) = A(1, n-1)+1 = ... = A(1, n-n)+n = A(1, 0)+n = A(0, 1)+n = 1+1+n = n+2, not 2n as claimed above. (Note that A(1, n) = A(0, A(0, ... A(0, 1)...)), again not as above).

Since we know A(1, n), A(2, n) = A(1, A(2, n-1)) = A(2, n-1)+2 = ... = A(2, n-n)+2n = A(2, 0)+2n = A(1, 1)+2n = 1+2+2n = 2n+3.

Similarly, A(3, n) = 2n+3-3 (that's 2**(n+3)-3), and A(4, n) = 2^^(n+3)-3 (where ^^ is the iterated power operation). You can greatly speed up the program above by adding cases for these.

My favorite number is A(4, 2).

Log in or register to write something here or to contact authors.