patternMinor
What does the exact $\mu$-recursive program for minimization look like?
Viewed 0 times
exactthewhatprogramminimizationlooklikerecursivefordoes
Problem
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.
$
\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.
Solution
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.
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.
Context
StackExchange Computer Science Q#60720, answer score: 7
Revisions (0)
No revisions yet.