$\mu$-operator

$\mu$ on predicates

Let a property on non-negative integers be given. Informally, the $\mu$-operator looks for the smallest number satisfying the given property. The $\mu$-operator is also known as the (unbounded) minimization operator or the (unbounded) search operator. Formally,

Definition. Let $\mathrm{\Phi }(𝒙,y)$ be an $(m+1)$-ary predicate (property) over $\mathbb{N}$, the set of natural numbers ($0$ included here), with $m$ a non-negative integer ($𝒙$ is $m$-ary). Define

$$A_{\mathrm{\Phi }}(𝒙):=\{y\in \mathbb{N}\mid \mathrm{\Phi }(𝒙,y)\},$$

The $\mu$-operator on $\mathrm{\Phi }$ is given by

The notation $\mu y\mathrm{\Phi }(𝒙,y)$ reads “the smallest $y$ such that $\mathrm{\Phi }(𝒙,y)$ is satisfied”. Note that $y$ is used both as a variable and a number that the variable $y$ represents.

Note that $\mu y\mathrm{\Phi }(𝒙,y)$ is a partial function on $𝒙$ ($y$ is a bounded variable). In other words, the $\mu$-operator is a function that takes an $m+1$-ary predicate to an $m$-ary partial function. When $m=0$, $\mu$ is either an integer, or $\mathrm{\varnothing }$.

For example, suppose $\mathrm{\Phi }(x,y)$ is the property $(x-y)(x+y)\ge 10$. Then $\mu y\mathrm{\Phi }(x,y)=0$ iff $x\ge 4$, and undefined otherwise.

The reason why the $\mu$-operator is called the search operator comes from recursive function theory. The search for the smallest $y$ such that $\mathrm{\Phi }(𝒙,y)$ begins with testing for $\mathrm{\Phi }(𝒙,0)$. If the test fails ($\mathrm{\Phi }(𝒙,0)$ is false), then testing for $\mathrm{\Phi }(𝒙,1),\mathrm{\Phi }(𝒙,2),\mathrm{\Phi }(𝒙,3),\mathrm{\cdots }$ are successively performed. The testing stops when a $y$ with $\mathrm{\Phi }(𝒙,y)$ is found. This $y$ is also the smallest $y$ satisfying $\mathrm{\Phi }$. Nevertheless, the testing can conceivably go on indefinitely, hence the name unbounded. There is also a bounded version of $\mu$-operation:

Definition. Let $\mathrm{\Phi }(𝒙,y)$ be given as above. Define

$$A_{\mathrm{\Phi }}(𝒙,y):=\{z\in \mathbb{N}\mid \mathrm{\Phi }(𝒙,z)\text{ and }z\le y\}.$$

The bounded $\mu$-operator on $\mathrm{\Phi }$ is given by

Thus the bounded $\mu$-operator takes an $(m+1)$-ary predicate (on $(𝒙,z)$, where $z$ is a free variable) to an $(m+1)$-ary total function (on $(𝒙,y)$, as $z$ is now bounded by $\mu$).

$\mu$ on total functions

The $\mu$ operator can also be defined on functions. We first discuss the case of $\mu$ on total functions.

Definition. Given a total $(m+1)$-ary function $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$, define

$$A_f(𝒙):=\{y\in \mathbb{N}\mid f(𝒙,y)=0\},$$

The $\mu$-operator on $f$ is given by

This definition is actually equivalent to the one regarding predicates, in the following sense: given a total function $f$ with arity $m+1$, define predicate ${\mathrm{\Phi }}_f(𝒙,y)$ of arity $m+1$, as “$f(𝒙,y)=0$”. Then

$$\mu yf(𝒙,y)=\mu y{\mathrm{\Phi }}_f(𝒙,y).$$

Conversely, given an $(m+1)$-ary predicate $\mathrm{\Phi }(𝒙,y)$, define an $(m+1)$-ary function $f_{\mathrm{\Phi }}(𝒙,y):=1\dot{-}{\chi }_{\mathrm{\Phi }}(𝒙,y)$, where ${\chi }_{\mathrm{\Phi }}$ is the characteristic function of $\mathrm{\Phi }$. Then

$$\mu y\mathrm{\Phi }(𝒙,y)=\mu y{f}_{\mathrm{\Phi }}(𝒙,y).$$

Note also that $\mu f$ may be partial even if $f$ is total, since it is possible $f(𝒙,y)\ne 0$ for all $y$, and the search will go on indefinitely. For example, let $f(x,z,y)=x^2+z^2-y^2$ if $x^2+z^2\ge y^2$, and $1$ otherwise. Clearly, $f$ is a total function. It is easy to see that $\mu yf(3,4,y)=5$, while $\mu yf(1,2,y)$ is undefined.

$\mu$ on partial functions

The definition of the $\mu$-operator on total functions can be generalized to partial functions. However, in recursive functions theory, an additional condition is imposed in order to make the generalization.

Definition. Given a partial $(m+1)$-ary function $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$, define

$$A_f(𝒙):=\{y\in \mathbb{N}\mid f(𝒙,y)=0\text{ and }(𝒙,z)\in \mathrm{dom}(f)\text{ for all }z\le y\},$$

The $\mu$-operator on $f$ is given by

The extra condition that $f(𝒙,z)$ be defined for all $z\le y$ is needed in order to avoid situations where testing for $f(𝒙,z)=0$ gets stuck in an infinite loop (in a Turing machine or a URM) because $f(𝒙,z)$ is undefined, before $y$ is ever reached for testing. If we drop this extra condition, then it is possible to find a partial recursive function $f$ such that $\mu f$ is not recursive.

Remarks.

• Bounded $\mu$-operator may also be defined on functions. In the case of partial functions, the definition can be given as follows: let $f(𝒙,y)$ be an $(m+1)$-ary partial function, with

  $$A_f(𝒙,y):=\{z\in \mathbb{N}\mid f(𝒙,z)=0,z\le y,\text{ and }(𝒙,t)\in \mathrm{dom}(f)\text{ for all }t\le z\},$$

  then

• Given the set $𝒫ℛ$ of primitive recursive functions, one obtains the set $ℛ$ of recursive functions by taking the closure of $𝒫ℛ$ with respect to the application of the $\mu$-operator. Furthermore, if $f\in ℛ$, so is $\mu f\in ℛ$, and it can be shown that any recursive function can be obtained from primitive recursive functions by no more than one application of the $\mu$-operator. This is known as the Kleene normal form theorem.

• With respect to the bounded $\mu$-operator, any primitive recursive function (or predicate) stays primitive recursive after an application of the bounded $\mu$, and any total recursive function stays total after an application of the bounded $\mu$.

Title	$\mu$-operator
Canonical name	muoperator
Date of creation	2013-03-22 19:05:47
Last modified on	2013-03-22 19:05:47
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	12
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03D20
Synonym	minimization operator
Synonym	minimization-operator
Synonym	search operator
Synonym	search-operator