Least-number operator

$\mu$-operator, minimization operator

A device for constructing new functions out of others, as follows. Let $g$ be an $(n+1)$-ary arithmetic function, i.e. a function with arguments and values in the set of natural numbers. It is assumed here that $g$ is a partial function, i.e. it is not necessarily defined for all values of its arguments. One says that the $n$-ary arithmetic function $f$ is obtained from $g$ by the least-number operator if, for any natural numbers $k_1,\ldots,k_n,k$,

$$f(k_1,\ldots,k_n)=k$$

if and only if the values of $g(k_1,\ldots,k_n,l)$ are defined and are not equal to zero for all $l<k$, while $g(k_1,\ldots,k_n,k)$ is defined and equals zero. If $f$ is obtained from $g$ by the least-number operator, one writes

$$f(x_1,\ldots,x_n)=\mu y[g(x_1,\ldots,x_n,y)=0].$$

An important property of the least-number operator is the following: If $g$ is a computable function, then the above function $f$ is always partially computable. In fact, if there is an algorithm computing $g$, then the value of $f(x_1,\ldots,x_n)$ can be computed as follows. Compute $g(x_1,\ldots,x_n,0)$. If the computation process ends, i.e. if $g(x_1,\ldots,x_n,0)$ is defined, and if $g(x_1,\ldots,x_n,0)=0$, put $f(x_1,\ldots,x_n)=0$; but if $g(x_1,\ldots,x_n,0)\neq0$, begin to compute $g(x_1,\ldots,x_n,1)$. If the process ends and $g(x_1,\ldots,x_n,1)=0$, put $f(x_1,\ldots,x_n)=1$; but if $g(x_1,\ldots,x_n,1)\neq0$, proceed to compute $g(x_1,\ldots,x_n,2)$; etc. The computation will come to an end if there exists a $y$ such that, for all $z<y$, $g(x_1,\ldots,x_n,z)$ is defined and not zero, while $g(x_1,\ldots,x_n,y)$ is defined and equal to zero. Then $f(x_1,\ldots,x_n)=y$.

The least-number operator plays an important role in the definition of the class of partial recursive functions (cf. Partial recursive function).

References

[a1]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165