Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1 / 4J (Automata and Formal Languages)

The basic functions are zero $Z(\mathbf{x})=0$, successor $S(n)=n+1$, and projections $P_i^k(\mathbf{x})=x_i$. Close these under composition and primitive recursion:

Define $A(0,m)=m$ and $A(n+1,m)=S(A(n,m))$. This is primitive recursion from a projection and successor, so $A(n,m)=n+m$ is primitive recursive function.

If $f$ is primitive recursive, then $d(n)=f(P_1^1(n),P_1^1(n))$ is obtained by composition with projections. Hence the diagonal is primitive recursive.

Assume a complete list $f$ were primitive recursive. Closure under diagonal composition and successor makesprimitive recursive. Completeness gives a row $n$ with $f(n,k)=d(k)$ for every $k$, but at $k=n$ this says $f(n,n)=f(n,n)+1$. This is the diagonal argument.