[Answers] What does the exact $\mu$-recursive program for minimization look like?

Problem Detail: 

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.

Asked By : lo tolmencre

Answered By : Andrej Bauer

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60720

3.2K people like this

 Download Related Notes/Documents