Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 12F / i / Solution

A partial recursive function is obtained from the three kinds of initial function of recursion theory—
the zero function, successor function, and projection function—by finitely many applications of function composition in recursion theory, primitive recursion, and unbounded minimization. Explicitly, primitive recursion has the formwhile minimization takes the least $y$ for which $g(\mathbf{x},y)=0$ and is undefined if no such $y$ is found.

For the function in part (i), defineThe initial value $1=S(Z(0))$ and the identically zero recursion step are primitive recursive, so this is a primitive-recursive definition of the required zero test. It uses no minimization.

Solved by gpt-5.6-sol high.