Orchid XP v8 wrote:
> What is Ackermann's function, why does it grow so fast, and why does 
> anybody care anyway?
> 
> (I'm hoping you can explain this better than Wikipedia...)
> 

I'm not Darren, and he'd probably be more familiar with this than I, but 
here's what I recall.

The class of computable functions (also known as recursive functions) 
are something that you're familiar with.  Considered in their most basic 
context, these are all functions which take a natural number as input, 
provides an integer as output, and which you could write a computer 
program to compute.  If there's a program which can compute this 
function for each possible natural number (in other words, it always 
halts), then you have a total computable function.

Way back in the early days of people starting to understand this sort of 
stuff -- before diagionalization proofs were used for this sort of 
thing, there was a conjecture that this class of total computable 
functions was equivalent to the class of what are called primitive 
recursive functions.  You can think of a primitive recursive function, 
basically (iirc), as any function you could code up if only allowed for 
loops which didn't change their loop bounds during their execution (no 
recursion and no while loops either obviously).

While it seems "obvious" since you're familiar with diagonalization type 
arguements, that this class is strictly smaller than the class of total 
computable functions, you can get a bit of an idea for why people made 
this confusion if you attempt to actually think of a function which is 
total computable but not primitive recursive.  Almost all the function 
you normally deal with (addition, subtraction, division, factorial, 
exponentiation, etc) are all primitive recursive.

Here's where the Ackermann function comes in.  It's obviously a total 
computable function, yet you can show that it cannot be primitive 
recursive.  The essence of this argument is that the growth rate of the 
Ackermann function is larger than what could be achieved by any 
primitive recursive function.  I believe that the Ackermann function was 
the first concrete example of a well defined total computable function 
which was not primitive recursive -- hence why people care about it.

If you're curious as to why it grows so quickly, I suggest you code it 
up and examine it's behavior for a bit.  It's an enjoyable exercise in 
experimentally poking around in the guts of a rather odd mathematical 
function.


Fun Fact! The union-find data structure has as an amortized complexity 
bound for many of many of its operations a running time proportional to 
the *inverse* of the Ackermann function! which is the slowest growing 
non-constant big-O of any algorithm I'm aware of (though I've explicitly 
never looked for others).

Post a reply to this message