You are here
HomeAckermann function is not primitive recursive
Primary tabs
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.
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.
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 nonnegative integers $(x_{1},\ldots,x_{n})$ for some $n$, and $x=\max\{x_{1},\ldots,x_{n}\}$. Likewise for $\boldsymbol{y}$ and $y$.
1. We show that the zero function, the successor function, and the projection functions are in $\mathcal{A}$.

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

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

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

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})<A(r_{i},x)$, and $h(\boldsymbol{y})<A(s,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})<A(s,g_{j}(\boldsymbol{x}))<A(s,A(r_{j},x))<A(s+r_{j}+2,x)$, 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 $g(\boldsymbol{x})<A(r,x)$ and $h(\boldsymbol{y})<A(s,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)<A(q,n+x),\quad\mbox{for some }q\mbox{ not depending on }x% \mbox{ and }n.$ Pick $q=1+\max\{r,s\}$, and induct on $n$. First, $f(\boldsymbol{x},0)=g(\boldsymbol{x})<A(r,x)<A(q,x)$. Next, suppose $f(\boldsymbol{x},n)<A(q,n+x)$. Then $f(\boldsymbol{x},n+1)=h(\boldsymbol{x},n,f(\boldsymbol{x},n))<A(s,z)$, where $z=\max\{x,n,f(\boldsymbol{x},n)\}$. By the induction hypothesis, together with the fact that $\max\{x,n\}\leq n+x<A(q,n+x)$, we see that $z<A(q,n+x)$. Thus, $f(\boldsymbol{x},n+1)<A(s,z)<A(s,A(q,n+x))\leq A(q1,A(q,n+x))=A(q,n+1+x)$, proving the claim.
To finish the proof, let $z=\max\{x,y\}$. Then, by the claim, $f(\boldsymbol{x},y)<A(q,x+y)\leq A(q,2z)<A(q,2z+3)=A(q,A(2,z))=A(q+4,z)$, 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. ∎
Mathematics Subject Classification
03D75 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
typo?
Hi, I’m arishiki. I’m new to this site, so I’m afraid I would do some inappropriate things. If so, please notice on me.
Thank you for great entry, CWoo. But I think $A(q,A(2,z))=A(q+4,z)$ at the last of the proof would be a mistake and you should have meant $A(q,A(2,z))<A(q+4,z)$.
Thank you.
@arishiki  you can use LaTeX in forum posts
Hi Arishiki  Welcome to the site. You can use LaTeX in forum posts and pretty much everywhere…