Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 12F (Automata and Formal Languages)

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.

Using the zero test $s$ from part (i), define by primitive recursionSince $s(0)=1$ and $s(1)=0$, the values alternate:Thus $r$ is the required parity function and, like $s$, is primitive recursive without minimization.

Let $g(n,k)=r(n)$, where $r$ is the total primitive-recursive parity function from part (ii), and apply unbounded minimization in $k$:If $n$ is even, then $g(n,0)=0$ and $p(n)=0$. If $n$ is odd, then $g(n,k)=1$ for every $k$, so the search never terminates and $p(n)$ is undefined. Hence $p$ is partial recursive. Because every function built without minimization is total, $p$ cannot be defined without minimization; the functions $s$ and $r$ can.

It remains to characterize the functions built using only the initial functions and composition. They are exactly the functionsfor some $c\in \mathbb{N}$ and some input coordinate $i$.

Indeed, the zero function is the first form, the successor function and each projection function have the second form, and composing functions of these forms preserves the classification: a constant outer function remains constant, while an outer function $y_j+c$ selects one inner function and adds $c$. This proves necessity by structural induction. Conversely, applying the successor function $c$ times to zero produces the constant $c$, and applying it $c$ times to ${\pi }_i^k$ produces $x_i+c$.

Every function in this class is directly computable: an algorithm either writes the fixed constant $c$, or copies the $i$th input and performs $c$ successor steps.