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


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

  • $\begingroup$ 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) $\endgroup$ – Bert Zangle Sep 15 '16 at 16:08
  • $\begingroup$ (b) Right, the 'inverse' remark (and thought) was pretty bold I realized right after writing it. But: the discussion you link to is actually an example of the inverse being "easier" than the function. Would you happen to know (or have an intuition) whether the opposite can be the case: a function that is prf, while its inverse isn't? Since that was the idea I had in mind in my point 3. above: multiplication is prf, so its inverse cannot be not prf. (2/2) $\endgroup$ – Bert Zangle Sep 15 '16 at 16:08
  • $\begingroup$ @BertZangle Re: (b), reverse the example: the inverse of the Ackermann function is simple, but its inverse isn't. Re: (a), it's just because primitive recursion doesn't have any mechanism to tell a computation to diverge (= never halt). In some sense, expanding primitive recursion by including the never-defined function wouldn't change the class too much (and would allow partial functions); but that is indeed something which primitive recursion can't do on its own. $\endgroup$ – Noah Schweber Sep 15 '16 at 17:12
  • $\begingroup$ 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. $\endgroup$ – Bert Zangle Sep 15 '16 at 18:30
  • $\begingroup$ @BertZangle Yes, that sounds right. Every p.r. function comes equipped with a "clock" that counts down on any input; and once the clock reaches zero, the function outputs a value. $\endgroup$ – Noah Schweber Sep 15 '16 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.