= Solution
A <partial recursive function> is obtained from the three kinds of <initial function of recursion theory>—
the <zero function>, <successor function>, and <projection functions>[projection function]—by finitely many applications of <function composition in recursion theory>, <primitive recursion>, and <unbounded minimization>. Explicitly, primitive recursion has the form
$$
f(\mathbf x,0)=g(\mathbf x),
\qquad
f(\mathbf x,n+1)=h(\mathbf x,n,f(\mathbf x,n)),
$$
while 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), define
$$
s(0)=1,
\qquad
s(n+1)=0.
$$
The initial value $1=S(Z(0))$ and the identically zero recursion step are <primitive recursive function>[primitive recursive], so this is a primitive-recursive definition of the required zero test. It uses no minimization.
Back to article page
