= Solution
Let $g(n,k)=r(n)$, where $r$ is the total primitive-recursive parity function from part (ii), and apply <unbounded minimization> in $k$:
$$
p(n)=\mu k\,[g(n,k)=0].
$$
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 <composition-only recursive functions>[functions]
$$
\boxed{f(x_1,\ldots,x_k)=c
\quad\hbox{or}\quad
f(x_1,\ldots,x_k)=x_i+c}
$$
for 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 <total computable function>[computable]: an algorithm either writes the fixed constant $c$, or copies the $i$th input and performs $c$ successor steps.
Back to article page
