The Ackermann function
Haskell, 35
0%n=1+n
m%n=iterate((m-1)%)1!!(n+1)

this defines the operator function %.
this works by noticing that m%n (where a is the ackerman function) for nonzero m is (m-1)% applied n+1 times to 1. for example, 3%2 is defined as 2%(3%1) which is 2%(2%(3%0)), and this is 2%(2%(2%1))