Skip to main content
1 of 3
Klaus Draeger
  • 2.5k
  • 1
  • 23
  • 19

Breaking the Ackermann function all the way down to the elementary operators would really be quite lengthy, but here is a sketch:

Note that when computing $A(m,x)$ recursively, at any point of the computation you are dealing with an expression of the form $A(m_1,A(m_2,\dots,A(m_k,z)\dots)$. Given a bijective pairing function $p$ with inverse $(\pi_1,\pi_2)$, we can encode this state as $p(z,p(k,p(m_k,\dots,p(m_2,m_1)\dots)$ (just $p(z,0)$ in case $k=0$). We then can define the one-step evaluation function, given a state:

$e(p(z,0)) = p(z,0)$;

$e(p(z,p(k,p(0,c)))) = p(z+1,p(k-1,c))$;

$e(p(0,p(k,p(m+1,c)))) = p(1,p(k,p(m,c)))$;

$e(p(z+1,p(k,p(m+1,c)))) = p(z,p(k+1,p(m+1,p(m,c))))$.

Finally, starting with $p(x,p(1,m))$, wrap $\mu$-induction around $e$ to find the point where we get to a state of the form $p(z,0)$ - $z$ will be $A(m,x)$.

Klaus Draeger
  • 2.5k
  • 1
  • 23
  • 19