Μ operator

In computability theory, the μ operator, minimization operator, or unbounded search operator searches for the least natural number with a given property.

Definition

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 { 0, 1, 2, . . . }. 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::"

Kleene notes that any of the 6 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" 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, :"$(exists\; y)\; mu\; y\; R(y)\; =\; \{\; mbox\{the\; least\; (natural\; number)\}\; y\; mbox\{such\; that\}\; R(y)\}$" (p. 279, where "$(exists\; y)$" means "There exists a "y" such that..."

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.

For a given R(y) the unbounded mu operator μyR(y) (note no requirement for "(Ey)" ) can result in a total function or partial function. Kleene writes this potentially-partial function in a different way (cf. p. 317)::εyR(x, y) =::* the least y such that R(x,y) [is true] , if (Ey)R(x,y)::* 0, otherwise.

Properties

(i) In context of the primitive recursive functions, where the search variable y of the μ-operator is bounded, e.g. yy R( y, x₁,..., x_n ) is a primitive recursive function.

(ii) In the context of the (total) recursive functions: Where the search variable y is "unbounded" but guaranteed to exist for "all" values x_i of the total recursive predicate R's parameters,:(x₁), ..., (x_n) (Ey) R( y, x_i, ... x_n ) implies that μyR(y, x_i, ... x_n) is a total recursive function.:: here (x_i) means "for all x_i" and Ey means "there exists at least one value of y such that..." (cf Kleene (1952) p. 279.)

then the five primitive recursive operators plus the unbounded-but-total μ-operator give rise to what Kleene called the "general" recursive functions (i.e. total functions defined by the six recursion operators).

(iii) In the context of the partial recursive functions: Suppose that the relation "R" holds if and only if a partial recursive function converges to zero. And suppose that that partial recursive function converges (to something, not necessarily zero) whenever $mu\; y\; R(y,x\_1,ldots,x\_k)$ is defined and "y" is $mu\; y\; R(y,x\_1,ldots,x\_k)$ or smaller. Then the function $mu\; y\; R(y,x\_1,ldots,x\_k)$ is also a partial recursive function.

The μ operator is used in the characterization of the computable functions as the μ recursive functions.

Examples

Example #1: The bounded μ-operator is a primitive recursive function

:"In the following, to save space the bold-face x i.e. x will represent the string x_i, . . ., x_n."

The "bounded" μ-operator can be expressed rather simply in terms of two primitive recursive functions (hereafter "prf") that also are used to define the CASE function -- the product-of-terms Π and the sum-of-terms Σ (cf Kleene #B page 224). (As needed, any boundary for the variable such as s≤t or ts≤t f_s (x, s) = f₀(x, 0) * f₁(x, 1) * . . . * f_t(x, t):*Σ_{t gt ( x, t ) = g0( x, 0 ) + g1(x, 1 ) + . . . + gz-1(x, z-1 )}

Before we proceed we need to introduce a function ψ called "the representing function" of predicate R. Function ψ is defined from inputs ( t= "truth", f="falsity" ) to outputs ( 0, 1 ) ("Observe the order!"). In this case the input to ψ i.e. { t, f } is coming from the output of R::* ψ( R = t ) = 0:* ψ( R = f ) = 1 Kleene demonstrates that μy_{y R(y) is defined as follows; we see the product function Π is acting like a Boolean AND operator, and the sum Σ is acting somewhat like a Boolean OR but is producing { Σ≠0, Σ=0 } rather than just { 1, 0 }: : μy y R(y) = Σt Πs≤t ψ( R( x ,t ,s )) =:* [ ψ( x, 0, 0 ) ] + :* [ ψ( x, 1, 0 ) * ψ( x, 1, 1 ) ] +:* [ ψ( x, 2, 0 ) * ψ( x, 2, 1 ) * ψ( x, 2, 2 ) ] + :* . . . . . . +:* [ ψ( x, z-1, 0 ) * ψ( x, z-1, 1 ) * ψ( x, z-1, 2 ) + . . . + ψ ( x, z-1, z-1 ) ]}

:"Σ is actually a primitive recursion with the base Σ(x, 0) = 0 and the induction step Σ(x, y+1 ) = Σ( x, y ) + Π( x, y ). The product Π is also a primitive recursion Π with base step Π( x, 0 ) = ψ( x, 0 ) and induction step Π( x, y+1 ) = Π( x, y )*ψ( x, y+1 ).

The equation is easier if observed with an example, as given by Kleene. He just made up the entries for the representing function ψ(R(y)). He designated the representing functions χ(y) rather than ψ( x, y ):

The algorithm for the minimization operator μy [φ( x, y )] will, in essence, create a sequence of instances of the function φ( x, y ) as the value of parameter y (a natural number) increases; the process will continue (see Note † below) until a match occurs between the output of function φ( x, y ) and some pre-established number (usually 0). Thus the evaluation of φ(x, y) requires, at the outset, assignment of a natural number to each of its variables x and an assignment of a "match-number" (usually 0) to a register "w", and a number (usually 0) to register y.

:"Note †: The "unbounded" μ operator will continue this attempt-to-match process ad infinitum or until a match occurs. Thus the "y" register must be unbounded -- it must be able to "hold" a number of arbitrary size. Unlike a "real" computer model, abstract machine models allow this. In the case of a "bounded" μ operator, a lower-bounded μ operator would start with the contents of y set to a number other than zero. An upper-bounded μ operator would require an additional register "ub" to contain the number that represents the upper bound plus an additional comparison operation; an algorithm could provide for both lower- and upper bounds."

In the following we are assuming that the Instruction Register (IR) encounters the μy "routine" at instruction number "n". Its first action will be to establish a number in a dedicated "w" register -- an "example of" the number that function φ( x, y ) must produce before the algorithm can terminate (classically this is the number zero, but see the footnote about the use of numbers other than zero). The algorithm's next action at instructiton "n+1" will be to clear the "y" register -- "y" will act as an "up-counter" that starts from 0. Then at instruction "n+2" the algorithm evaluates its function φ( x, y ) -- we assume this takes j instructions to accomplish -- and at the end of its evaluation φ( x, y ) deposits its output in register "φ". At the n+j+3rd instruction the algorithm compares the number in the "w" register (e.g. 0) to the number in the "φ" register -- if they are the same the algorithm has succeeded and it escapes through "exit"; otherwise it increments the contents of the "y" register and "loops" back with this new y-value to test function φ( x, y ) again.

References

*Stephen Kleene (1952) "Introduction to Metamathematics", North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint).

*Marvin L. Minsky (1967), "Computation: Finite and Infinite Machines", Prentice-Hall, Inc. Englewood Cliffs, N.J. :On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

*George Boolos, John Burgess, Richard Jeffrey (2002), "Computability and Logic: Fourth Edition", Cambridge University Press, Cambridge, UK. Cf pp. 70-71.