Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 12I / Solution

The primitive recursive functions are the smallest class containing zero, successor, and projections and closed under composition and primitive recursion. Addition is defined byand multiplication byThus both are primitive recursive directly from the definition. Inductively,is primitive recursive. For fixed $a$,so $E_a(n)=a^n$ is primitive recursive.

Encode $(x_0,\dots ,x_{k-1})$ by $2^{x_0}{3}^{x_1}\cdots p_k^{x_{k-1}}$. The exponent functions $M_{p_i}$ decode the coordinates. Thereforeis a primitive recursive one-number encoding of $F$; the finite product is built from the primitive recursive multiplication and exponentiation just established.

The Fibonacci function is primitive recursive. Encode the pair $(B(n),B(n+1))$ byStarting with $C(0)=3$, primitive recursion usingconstructs $C$, and $B(n)=M_2(C(n))$.

There is no universal exponential bound of the stated form. The primitive recursive functionexceeds $R^n$ for every fixed $R>0$ once $n$ is sufficiently large.