# Not sure if minimization is needed for definition of function 'half', or if primitive recursive definition possible

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:

1. $\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?

2. 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?

3. 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'}$?

• Thanks! Two questions, if you allow: (a) I'm still struggling to accept that $\mathbf{half}$ (the original function) cannot be primitive recursive (prf): prf's are total not by stipulation but because it follows from their definition. So, I know, my attempt will be futile, but what I have in mind is using bounded $\mu$ in $\mathbf{half}$ for even $x$, and defining output for odd $x$ as undefined i.e. "diverges". Which I'm sure you will tell me I cannot do. But why? I can distinguish cases by prf, and why not also write an "infinite loop" (Turing style) for "undefined"? (1/2) – Bert Zangle Sep 15 '16 at 16:08
• Re Re: (a). Is it (approximately, and informally) correct to say that the reason for this (not being able to define divergence with prf) is because, given the definition of prim. rec. (e.g. scheme V in Soare), no matter what tricks I might try (e.g. conditionals to create some loop), the recursive "counter" of $f$, i.e. $x_1$ in $f(x_1, \vec{x})$ inevitably goes to the 0 base case, which I can't prevent since it's part of the scheme. And at that point I must "commit" to some value, be that a constant, or the output of another prf function, so the function will not "loop", so it will be total. – Bert Zangle Sep 15 '16 at 18:30