Ackermann — total, computable, but not primitive recursive

Parent: recursive-functions

The classic witness that primitive recursion ⊊ total computable: a function you can obviously compute, that no for-loop program can.

Ackermann function

A(0, n) = n + 1 A(m+1, 0) = A(m, 1) A(m+1, n+1) = A(m, A(m+1, n)) The last line recurses inside its own argument — nesting, not a plain counter.

It is total (every call terminates — the pair (m,n) strictly decreases in lexicographic order) and clearly computable (just follow the rules).

Theorem

A is not primitive recursive Ackermann grows faster than every primitive recursive function.

Proof

The engine is a domination lemma: every p.r. function is capped by a single Ackermann level. We use standard monotonicity of A (each proved by induction): A(m,n) > n; A is strictly increasing in each argument; and level absorption A(a, A(b,n)) ≤ A(max(a,b)+2, n) — nesting two levels costs only a constant.

Lemma. For every primitive recursive f(x₁,…,xₖ) there is a fixed level t with f(x⃗) < A(t, max(x⃗)) for all inputs.

Proof by structural induction on the build of f.

• Base. zero = 0, successor = A(0,x), projections ≤ max(x⃗) — all < A(1, max(x⃗)).
• Composition f = g(h₁,…,hⱼ). By IH each hᵢ < A(u, max(x⃗)) (take u the largest) and g < A(s, max of its args). Then f < A(s, A(u, max(x⃗))) ≤ A(max(s,u)+2, max(x⃗)) by level absorption — a fixed level.
• Primitive recursion f(0,x⃗)=g(x⃗), f(n+1,x⃗)=h(n,f(n,x⃗),x⃗), with g < A(p,·), h < A(q,·) by IH. Unroll: applying (something bounded by) A(q,·) once per step, n steps deep. But A(q,·) iterated n times stays below A(q+1, n+·) — exactly the recurrence A(q+1, n+1) = A(q, A(q+1, n)). So f < A(q+2, n + max(x⃗)) — again a fixed level.

Every construction raises the needed level by only a constant, so any fixed p.r. f lands under one fixed level t. ∎ (lemma)

Now diagonalize. Suppose A were primitive recursive. Then g(n) = A(n,n) + 1 is p.r. (compose A with the diagonal), so the lemma gives a fixed t with g(n) < A(t, n) for all n. Set n = t: A(t,t) + 1 = g(t) < A(t, t) — a contradiction. So A is not primitive recursive. ∎

The moral: a p.r. function is trapped at some fixed rung t of the hierarchy A(0,·), A(1,·), A(2,·), …; A(n,n) walks up the rungs with n, so it escapes every fixed rung.

The growth is violent: A(4,2) already has 19,729 decimal digits. The extra power comes from the nested recursion — exactly what a bounded counter can't express, and a hint of the unbounded search of general-recursion. (A itself is still total; you don't yet need non-termination — but you've left the for-loop world.)