# Ackermann function is not primitive recursive

In this entry, we show that the Ackermann function $A(x,y)$, given by

 $A(0,y)=y+1,\qquad A(x+1,0)=A(x,1),\qquad A(x+1,y+1)=A(x,A(x+1,y))$

is not primitive recursive. We will utilize the properties of $A$ listed in this entry (http://planetmath.org/PropertiesOfAckermannFunction).

The key to showing that $A$ is not primitive recursive, is to find a properties shared by all primitive recursive functions, but not by $A$. One such property is in showing that $A$ in some way “grows” faster than any primitive recursive function. This is formalized by the notion of “majorization”, which is explained here (http://planetmath.org/SuperexponentiationIsNotElementary).

###### Proposition 1.

Let $\mathcal{A}$ be the set of all functions majorized by $A$. Then $\mathcal{PR}\subseteq\mathcal{A}$.

###### Proof.

We break this up into three parts: show all initial functions are in $\mathcal{A}$, show $\mathcal{A}$ is closed under functional composition, and show $\mathcal{A}$ is closed under primitive recursion. The proof is completed by realizing that $\mathcal{PR}$ is the smallest set satisfying the three conditions.

In the proofs below, $\boldsymbol{x}$ denotes some tuple of non-negative integers $(x_{1},\ldots,x_{n})$ for some $n$, and $x=\max\{x_{1},\ldots,x_{n}\}$. Likewise for $\boldsymbol{y}$ and $y$.

1. 1.

We show that the zero function, the successor function, and the projection functions are in $\mathcal{A}$.

• $z(n)=0, so $z\in\mathcal{A}$.

• $s(n)=n+1, so $s\in\mathcal{A}$.

• $p_{m}^{k}(x_{1},\ldots,x_{k})=x_{m}\leq x, so $p_{m}^{k}\in\mathcal{A}$.

2. 2.

Next, suppose $g_{1},\ldots,g_{m}$ are $k$-ary, and $h$ is $m$-ary, and that each $g_{i}$, and $h$ are in $\mathcal{A}$. This means that $g_{i}(\boldsymbol{x}), and $h(\boldsymbol{y}). Let

 $f=h(g_{1},\ldots,g_{m}),\quad\mbox{and}\quad g_{j}(\boldsymbol{x})=\max\{g_{i}% (\boldsymbol{x})\mid i=1,\ldots,m\}.$

Then $f(\boldsymbol{x}), showing that $f\in\mathcal{A}$.

3. 3.

Finally, suppose $g$ is $k$-ary and $h$ is $(k+2)$-ary, and that $g,h\in\mathcal{A}$. This means that $g(\boldsymbol{x}) and $h(\boldsymbol{y}). We want to show that $f$, defined by primitive recursion via functions $g$ and $h$, is in $\mathcal{A}$.

We first prove the following claim:

 $f(\boldsymbol{x},n)

Pick $q=1+\max\{r,s\}$, and induct on $n$. First, $f(\boldsymbol{x},0)=g(\boldsymbol{x}). Next, suppose $f(\boldsymbol{x},n). Then $f(\boldsymbol{x},n+1)=h(\boldsymbol{x},n,f(\boldsymbol{x},n)), where $z=\max\{x,n,f(\boldsymbol{x},n)\}$. By the induction hypothesis, together with the fact that $\max\{x,n\}\leq n+x, we see that $z. Thus, $f(\boldsymbol{x},n+1), proving the claim.

To finish the proof, let $z=\max\{x,y\}$. Then, by the claim, $f(\boldsymbol{x},y), showing that $f\in\mathcal{A}$.

Since $\mathcal{PR}$ is by definition the smallest set containing the initial functions, and closed under composition and primitive recursion, $\mathcal{PR}\subseteq\mathcal{A}$. ∎

As a corollary, we have

###### Corollary 1.

The Ackermann function $A$ is not primitive recursive.

###### Proof.

Otherwise, $A\in\mathcal{A}$, which is impossible. ∎

Title Ackermann function is not primitive recursive AckermannFunctionIsNotPrimitiveRecursive 2013-03-22 19:07:29 2013-03-22 19:07:29 CWoo (3771) CWoo (3771) 11 CWoo (3771) Theorem msc 03D75 AckermannFunctionIsTotalRecursive