Mu Recursion

computation

Definition

Definition

${\mu }_0$ Operator

Let $g:{\mathbb{N}}^{k+1}\to \mathbb{N}$ ($k\ge 0$) be a total function. Then:

$$f={\mu }_{0}g:{\mathbb{N}}^k\to \mathbb{N}$$

is defined as $f(x_1,\dots ,x_k)={\min }_{y\ge 0}[g(y,x_1,\dots ,x_k)=0]$.

;

Link to original

Definition

$\bar{\mu }$ Operator

Let $g:{\mathbb{N}}^{k+1}\to \mathbb{N}$ ($k\ge 0$) be a total function. Then:

$$f=\bar{\mu }g:{\mathbb{N}}^{k+1}\to \mathbb{N}$$

is defined as $f(x_1,x_2,\dots ,x_{k+1})={\min }_{y\ge 0}[g(y,x_1,\dots ,x_{k+1})=x_1]$.

Link to original

Examples

Example

\begin{aligned} (\mu_{0} P_{1}^1)(n) = \min_{y \geq 0}[y = 0] = 0 \implies \mu_{0} P_{1}^1 = C_{0}^0 \\ \\ (\bar{\mu} P_{1}^1)(n) = min_{y \geq 0} [y = n] = n \implies \bar{\mu}P_{1}^1 = P_{1}^1

\end{aligned}

Example

$$\begin{array}{r}({\mu }_{0}S)(n)=\underset{y\ge 0}{\min }[y+1=0]=\text{undefined}\\ \\ (\bar{\mu }S)(n)=\underset{y\ge 0}{\min }[y+1=n]=\text{undefined for }n=0\end{array}$$