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,A(x+1,0)=A(x,1),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 $\mathrm{A}$ be the set of all functions^{} majorized by $A$. Then $\mathrm{P}\mathit{}\mathrm{R}\mathrm{\subseteq}\mathrm{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{P}\mathcal{R}$ is the smallest set satisfying the three conditions.
In the proofs below, $\bm{x}$ denotes some tuple of nonnegative integers $({x}_{1},\mathrm{\dots},{x}_{n})$ for some $n$, and $x=\mathrm{max}\{{x}_{1},\mathrm{\dots},{x}_{n}\}$. Likewise for $\bm{y}$ and $y$.

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

–
$$, so $z\in \mathcal{A}$.

–
$$, so $s\in \mathcal{A}$.

–
$$, so ${p}_{m}^{k}\in \mathcal{A}$.

–

2.
Next, suppose ${g}_{1},\mathrm{\dots},{g}_{m}$ are $k$ary, and $h$ is $m$ary, and that each ${g}_{i}$, and $h$ are in $\mathcal{A}$. This means that $$, and $$. Let
$$f=h({g}_{1},\mathrm{\dots},{g}_{m}),\text{and}\mathit{\hspace{1em}}{g}_{j}(\bm{x})=\mathrm{max}\{{g}_{i}(\bm{x})\mid i=1,\mathrm{\dots},m\}.$$ Then $$, showing that $f\in \mathcal{A}$.

3.
Finally, suppose $g$ is $k$ary and $h$ is $(k+2)$ary, and that $g,h\in \mathcal{A}$. This means that $$ and $$. 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:
$$ Pick $q=1+\mathrm{max}\{r,s\}$, and induct on $n$. First, $$. Next, suppose $$. Then $$, where $z=\mathrm{max}\{x,n,f(\bm{x},n)\}$. By the induction hypothesis, together with the fact that $$, we see that $$. Thus, $$, proving the claim.
To finish the proof, let $z=\mathrm{max}\{x,y\}$. Then, by the claim, $$, showing that $f\in \mathcal{A}$.
Since $\mathcal{P}\mathcal{R}$ is by definition the smallest set containing the initial functions, and closed under composition and primitive recursion, $\mathcal{P}\mathcal{R}\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 

Canonical name  AckermannFunctionIsNotPrimitiveRecursive 
Date of creation  20130322 19:07:29 
Last modified on  20130322 19:07:29 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Theorem 
Classification  msc 03D75 
Related topic  AckermannFunctionIsTotalRecursive 