Ackermann function

(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:

---

#!/usr/bin/perl

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";
$m=Math::BigInt->new($x);
$n=Math::BigInt->new($y);

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(1, n-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) = 2ⁿ⁺³-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).