TODO
The Ackermann function
The Ackermann function is a total function which is computable but not primitive recursive. A number of functions go by this name; a simple one is as follows: A(m,n)={n+1m=0A(m1,1)m>0n=0A(m1,A(m,n1))m>0n>0A(m, n) = \begin{cases} n + 1 & m = 0 \\ A(m-1, 1) & m > 0 \land n = 0 \\ A(m-1,A(m,n-1)) & m > 0 \land n > 0 \end{cases}
The rough outline for why AA is not primitive recursive is as follows:
Note that A(4,n)=2223A(4, n) = 2^{2^{\cdots^2}} - 3 with n+2n+2 exponentiations
To be primitive recursive, the function must be defined with a finite number of applications of primitive recursion
However, roughly, each exponentiation requires an application of primitive recursion
Thus, we cannot satisfy all nns
Skipping details, the reason that AA is not primitive recursive is that it can be shown to grow faster than any primitive recursive function
The Ackermann function is significant because:
It shows that the set of [[primitive recursive]] functions is smaller than the set of [[computable]] functions; i.e., primitive recursion is weaker than computability
Despite this, the Ackermann function is defined “simply” (i.e., using recursion)
Though it is not primitive recursive, the Ackermann function is a [[partial recursive]] function



Referenced by: