Ackermann function is not primitive recursive


In this entry, we show that the Ackermann functionMathworldPlanetmath 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 A be the set of all functionsMathworldPlanetmath majorized by A. Then PRA.

Proof.

We break this up into three parts: show all initial functions are in 𝒜, show 𝒜 is closed under functionalPlanetmathPlanetmathPlanetmath compositionMathworldPlanetmath, and show 𝒜 is closed under primitive recursion. The proof is completed by realizing that 𝒫 is the smallest set satisfying the three conditions.

In the proofs below, 𝒙 denotes some tuple of non-negative integers (x1,,xn) for some n, and x=max{x1,,xn}. Likewise for 𝒚 and y.

  1. 1.

    We show that the zero function, the successor function, and the projection functions are in 𝒜.

    • z(n)=0<n+1=A(0,n), so z𝒜.

    • s(n)=n+1<n+2=A(1,n), so s𝒜.

    • pmk(x1,,xk)=xmx<x+1=A(0,x), so pmk𝒜.

  2. 2.

    Next, suppose g1,,gm are k-ary, and h is m-ary, and that each gi, and h are in 𝒜. This means that gi(𝒙)<A(ri,x), and h(𝒚)<A(s,y). Let

    f=h(g1,,gm),andgj(𝒙)=max{gi(𝒙)i=1,,m}.

    Then f(𝒙)<A(s,gj(𝒙))<A(s,A(rj,x))<A(s+rj+2,x), showing that f𝒜.

  3. 3.

    Finally, suppose g is k-ary and h is (k+2)-ary, and that g,h𝒜. This means that g(𝒙)<A(r,x) and h(𝒚)<A(s,y). We want to show that f, defined by primitive recursion via functions g and h, is in 𝒜.

    We first prove the following claim:

    f(𝒙,n)<A(q,n+x),for some q not depending on x and n.

    Pick q=1+max{r,s}, and induct on n. First, f(𝒙,0)=g(𝒙)<A(r,x)<A(q,x). Next, suppose f(𝒙,n)<A(q,n+x). Then f(𝒙,n+1)=h(𝒙,n,f(𝒙,n))<A(s,z), where z=max{x,n,f(𝒙,n)}. By the induction hypothesis, together with the fact that max{x,n}n+x<A(q,n+x), we see that z<A(q,n+x). Thus, f(𝒙,n+1)<A(s,z)<A(s,A(q,n+x))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(𝒙,y)<A(q,x+y)A(q,2z)<A(q,2z+3)=A(q,A(2,z))=A(q+4,z), showing that f𝒜.

Since 𝒫 is by definition the smallest set containing the initial functions, and closed under composition and primitive recursion, 𝒫𝒜. ∎

As a corollary, we have

Corollary 1.

The Ackermann function A is not primitive recursive.

Proof.

Otherwise, 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