Μ 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 five primitive recursive operators makes it possible to define all computable functions (provided that the Church-Turing thesis is true).

Suppose that R( y, x₁, . . ., x_k ) is a fixed k+1-ary relation on the natural numbers. The mu operator "μy", in either the unbounded or bounded form, is a "number theoretic function" defined from the natural numbers to the natural numbers. However, "μy" contains a predicate over the natural numbers that delivers true when the predicate is satisfied and false when it is not.

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

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", "w ≤ y ≤ z". "When the indicated range contains no y such that R(y) [is "true"], the value of the "μy" expression is the cardinal number of the range"(p. 226); this is why the default "z" appears in the definition above. As shown below, the bounded mu operator "μy_y<z" is defined in terms of two primitive recursive functions called the finite sum Σ and finite product Π, a predicate function that "does the test" and a representing function that converts { t, f } to { 0, 1 }.

In Chapter XI §57 General Recursive Functions, Kleene defines the unbounded μ-operator over the variable y in the following manner,

In this instance R itself, or its representing function, delivers 0 when it is satisfied (i.e. delivers true); the function then delivers the number y. No upper bound exists on y, hence no inequality expressions appear in its definition.

...
Wikipedia