Ackermann Function

The Ackermann function is mathematically defined as:

The Ack function is well-defined total math function which is compute-able but not a primitive recursive function. Its value grow so quickly and become huge with small inputs. It is considered growing faster than exponential value, or even multi-exponential value.
The following is the table of values given small inputs for Ack function.

The Ack function can be easily programmed in most of the languages that support recursive definitions. The implementations are straightforward, similar as the above definition in math. For example, the VBScript implementation is like this.

1
2
3
4
5
6
7
8
9
10
11

Function Ack(M, N)
    If M = 0 Then
        Ack = N + 1
    Else
        If N = 0 Then
            Ack = Ack(M - 1, 1)
        Else
            Ack = Ack(M - 1, Ack(M, N - 1))
        End If
    End If
End Function

Function Ack(M, N)
    If M = 0 Then
        Ack = N + 1
    Else
        If N = 0 Then
            Ack = Ack(M - 1, 1)
        Else
            Ack = Ack(M - 1, Ack(M, N - 1))
        End If
    End If
End Function

The Ack function is often used to test the optimization levels of a compiler. With the native implementation, the Ack man will yield ‘stack-over-flow’ error for even small inputs like (4,3).

–EOF (The Ultimate Computing & Technology Blog) —