Mu operator

In computability theory, the μ-operator, minimization operator, or unbounded search operator searches for the least natural number with a given property. Adding the μ-operator to the primitive recursive functions makes it possible to define all computable functions.

Definition

Suppose that R(y, x1, ..., xk) is a fixed (k+1)-ary relation on the natural numbers. The μ-operator "μy", in either the unbounded or bounded form, is a "number theoretic function" defined from the natural numbers to the natural numbers. However, the definition of "μy" contains a predicate over the natural numbers, which can be thought of as a condition that evaluates to true when the predicate is satisfied and false when it is not.

The bounded μ-operator appears earlier in Kleene (1952) Chapter IX Primitive Recursive Functions, §45 Predicates, prime factor representation as:

"

μ

y

y

<

z

R

(

y

)

.

The least

y

<

z

such that

R

(

y

)

,

if

(

∃

y

)

y

<

z

R

(

y

)

;

otherwise

,

z

.

{\displaystyle \mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.}

" (p. 225)

Stephen Kleene notes that any of the six inequality restrictions on the range of the variable y is permitted, i.e. y < z, y ≤ z, w < y < z, w < y ≤ z, w ≤ y < z and w ≤ y ≤ z.