Ackermann's Theorem

ACKERMANN’S FUNCTION: Ackermann’s function is an example of a function that is mu-recursive but not primitive recursive. Mu-recursive functions are said to have the power of a Turing machine. It is defined as follows:

A(x, y) can be computed for every (x, y). Hence A (x,y) is a total function. But Ackermann’s function is not primitive recursive but recursive.

Example.1: Calculate A(1, 1) and A(1, 2) where A(x, y) represents Ackermann’s function.

Solution: We have Ackermann’s function given by