The minimization of a given primitive recursive function $f$ is computed by the following expression:

$ \newcommand{\pr}[2]{\text{pr}^{#1}_{#2}} \newcommand{\gpr}{\text{Pr}} \newcommand{\sig}{\text{sgn}} \text{Mn}[f] = \gpr[g, h] \circ (\pr{1}{1}, \pr{1}{1}) $

$g = \sig \circ f \circ (\pr{1}{1}, c^1_0)$

$h = \text{Cond}[\text{t}_\leqslant \circ (\pr{3}{3}, \pr{3}{2}), \pr{3}{3}, \text{Cond}[ \text{add} \circ (\text{t}_= \circ (\pr{3}{3}, \text{ suc} \circ \pr{3}{2}), f \circ (\pr{3}{1}, \text{suc} \circ \pr{3}{2})), \text{suc} \circ \pr{3}{2}, \text{suc} \circ \text{suc} \circ \pr{3}{2} ]]$

The first call to the function ($\text{Mn}[f] \circ (\pr{1}{1}, \pr{1}{1}) (n, k)$) will return at most k+1 and terminate for all inputs, if $f$ is total recursive.

A $\mu$-recursive search would not necessarily terminate, if no $z \leqslant k$ such that $f(n, z) = 0$. But I fail to see how that $\mu$-recursive expression would look in contrast to the above one, meaning $-$ what would the part of the expression look like, that makes the function not terminate.


I think you're confused about definitions. What you represented above is bounded minimization where we look for the least number $z$ below a given bound $k$ such that $f(n,z) = 0$. Such bounded minimization can be defined without any extra gadgets, using only primitive recursion.

The so-called $\mu$ operation performs unbounded search. It is not something we can define using primitive recursion. It is a new primitive operation which we add to primitive recursive functions to obtain recursive functions.

That is, if $f$ is a function of several arguments then $\mu(f)$ is a partial function which satisfies $$ \mu(f)(\vec{n}) = k \iff f(\vec{n},k) = 0 \land \forall j < k, f(n,k) \neq 0. $$ If there is no such $k$ then $\mu(f)(\vec{n})$ is undefined.

Every primitive recursive function is total. However, $\mu$ allows us to create non-total functions, for instance $\mu(f)(1)$, where $f(n,k) = 1$, is everywhere undefined. Therefore, $\mu$ is not something that can be defined using primitive recursion.

There are various mechanisms that exceed the power of primitive recursion which allow us to define $\mu$. One such is a general recursion, and another is a fixed-point operator.

| cite | improve this answer | |

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.