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.
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(q-1,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. ∎

Title	Ackermann function is not primitive recursive
Canonical name	AckermannFunctionIsNotPrimitiveRecursive
Date of creation	2013-03-22 19:07:29
Last modified on	2013-03-22 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