Ackermann Function

computation

Definition

Ackermann Function

The Ackermann function $Ack:{\mathbb{N}}^2\to \mathbb{N}$ is defined as:

$$\begin{array}{rl}Ack(0,n)& =n+1\\ Ack(m+1,0)& =Ack(m,1)\\ Ack(m+1,n+1)& =Ack(m,Ack(m+1,n))\end{array}$$

Computability

$Ack$ is computable and total, but not primitive-recursive.