The exercise for a recursion theory introduction asks to define a function $\mathbf{half}$ by the definitions of (primitive) recursion, without specifying whether the schemata of primitive recursion suffice or if unbounded search (or minimization) is needed. My questions (at the end) will be precisely about that last part. The function to be defined is:
\begin{align} \mathbf{half}(x) &= \left\{\begin{array}{l l} x/2 & \text{if $x$ is divisible by 2}\\ \text{undefined} & \text{otherwise}\\ \end{array}\right. \end{align}
One idea would be to use a (given) primitive recursive function for multiplication, and define $\mathbf{half}$ via minimization as follows:
\begin{align} h(0) = 0 \\ h(x+1) = \mu \;\! z \;\! (\mathbf{mult}(z, 2) = x+1) \end{align}
This seems to give the right results: $x/2$ if $x$ divisible by 2, undefined otherwise, since $\mu$ fails to find a natural number for which the predicate holds.
My question is: do we need to use the minimization scheme here, and if so, why?
Here are my own thoughts so far:
$\mathbf{half}$ as defined above is a partial function, which is already sufficient to conclude that the function cannot be primitive recursive, since p.r. functions are total. Correct so far?
What if we change the definition of $\mathbf{half}$ such that it becomes a total (but, admittedly, arithmetically wrong) function, say: \begin{align} \mathbf{half'}(x) &= \left\{\begin{array}{l l} x/2 & \text{if $x$ is divisible by 2}\\ \text{0} & \text{otherwise}\\ \end{array}\right. \end{align} $\mathbf{half'}$ is a total function, so the argument from point 1. above does not apply anymore, which excluded that a purely primitive recursive definition is possible. Can we now get the right results without minimization?
My (vague, and quite possibly: completely wrong) reasoning why I expected the function to be definable by primitive recursion alone is as follows:
The $\mu$ operator is introduced in the context of the Ackermann function, where we see that we cannot define (simultaneous) recursion over more than one variable by the basic recursive definition. This is then solved (for arbitrary number of variables of simultaneous recursion) by introducing minimization/unbounded search.
However, $\mathbf{half}$ or $\mathbf{half'}$ don't seem to be cases where recursion over more than one variable is necessary. It appears to be a case of finding a way to 'invert' the (primitive recursively defined) multiplication function, requiring nothing more complicated than what we used to define multiplication itself.
I don't know if my reasoning in 3. above makes any sense, but any pointers as to why my line of reasoning is wrong, or if it were to be correct, how we can define $\mathbf{half}$ or $\mathbf{half'}$ without minimization would be greatly appreciated.
(edit) Any chance that the solution might consist in using bounded minimization, which is p.r., for function $\mathbf{half'}$?
You are quite right that half is not primitive recursive, since it is not total. And you are also right in your guess that half' is primitive recursive, since bounded search is primitive recursive.
Re: point 3, though, you need to be careful with inverses . . .