Ackermann's Function

15 Apr 2014

I came across Ackermann's function in Chapter 1.

Wikipedia says -

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions are primitive recursive.

In MIT Scheme, the function can be represented as:

  (define (A x y)
    (cond ((= y 0) 0)
      ((= x 0) (* 2 y))
      ((= y 1) 2)
      (else (A (- x 1) (A x (- y 1))))

Here is the javascript equivalent

function ack(x, y) {
  if(y == 0) return 0
  else if(x == 0) return 2*y
  else if(y == 1) return 2
  else return ack(x-1, ack(x, y-1))

So, What is a total Computable function?

  • Any function f(x) that always terminates with an output for every value of x.
    As seen in Ackermann's function above, the function handles all values of the input parameters
    x and y with 3 equals checks y=0, x=0, y=1 and an else condition.

Ok, What is a Primitive recursive function?

Obviously, Ackermann's function is a non-primitive recursive function. The recursion grows much faster.
Not clear? try computing A(1, 10). Try running step by step. Now try A(4, 3).

The beauty of this function is,
(A 0 n) returns 2n
(A 1 n) returns 2^n
(A 2 n) returns 2^{2^{...^{2}}}, for n 2s

Due to its non-primitive recursive nature, Ackermann's Function is used as a benchmark of a compiler's ability
to optimize recursion.

I intend to write more about other interesting functions or things that I come across in SICP. Stay tuned!