Mu operator

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: :"\mu y_{y" (p. 225) Stephen Kleene notes that any of the six inequality restrictions on the range of the variable y is permitted, i.e. 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 μ-operator μyR(y) (note no requirement for "(\exists y)" ) is a partial function. Kleene makes it as a total function instead (cf. p. 317): \varepsilon yR(x,y) = \begin{cases} \text{the least } y \text{ such that } R(x,y), &\text{if } (\exists y)R(x,y)\\ 0, &\text{otherwise}. \end{cases} The total version of the unbounded μ-operator is studied in higher-order reverse mathematics in the following form: (\exists \mu^2)(\forall f^1)\big( (\exists n^0)(f(n)=0) \rightarrow f(\mu(f))=0 \big), where the superscripts mean that n is zeroth-order, f is first-order, and μ is second-order. This axiom gives rise to the Big Five system ACA0 when combined with the usual base theory of higher-order reverse mathematics. == Properties ==

(i) In the context of the primitive recursive functions, where the search variable y of the μ-operator is bounded, e.g. y yR(y, x1, ..., xn) 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 xi of the total recursive predicate R's parameters, :(x1),...,(xn) (\exists y) R(y, xi, ..., xn) implies that μyR(y, xi, ..., xn) is a total recursive function. :Here (xi) means "for all xi" and \exists y 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 for y, x1, ..., xn if and only if a partial recursive function is defined on y, x1, ..., xn and equal to zero. And suppose that that partial recursive function is defined (but not necessarily equal to zero) whenever μyR(y, x1, ..., xk) is defined and y is μyR(y, x1, ..., xk) or smaller. Then the function μyR(y, x1, ..., xk) is also a partial recursive function. (y_1,\ldots,y_k) there is some x such that R(x,y_1,\ldots,y_k), then the function \mu x R(x,y_1,\ldots,y_k) is total. If it is a total function and also a partial recursive function then it is a total recursive function.--> The μ-operator is used in the characterization of the computable functions as the μ-recursive functions. In constructive mathematics, the unbounded search operator is related to Markov's principle. == Examples ==

Example 1: The bounded μ-operator is a primitive recursive function :In the following x represents the string xi, ..., xn. 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 t s≤t fs(x, s) = f0(x, 0) × f1(x, 1) × ... × ft(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) (note 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 OR operator, and the sum Σ is acting somewhat like a Boolean AND 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)] :Note that Σ 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): Example 2: The unbounded μ-operator is not primitive-recursive The unbounded μ-operator—the function μy—is the one commonly defined in the texts. But the reader may wonder why the unbounded μ-operator is searching for a function R(x, y) to yield zero, rather than some other natural number. :In a footnote Minsky does allow his operator to terminate when the function inside produces a match to the parameter "k"; ''this example is also useful because it shows another author's format:'' ::"For μt[φ(t) = k]" (p. 210) The reason for zero is that the unbounded operator μy will be defined in terms of the function "product" Π with its index y allowed to "grow" as the μ-operator searches. As noted in the example above, the product Πx of a string of numbers ψ(x, 0) *, ..., * ψ(x, y) yields zero whenever one of its members ψ(x, i) is zero: :Πs = ψ(x, 0) * , ..., * ψ(x, y) = 0 if any ψ(x, i) = 0 where 0≤i≤s. Thus the Π is acting like a Boolean AND. The function μy produces as "output" a single natural number y = {0, 1, 2, 3, ...}. However, inside the operator one of a couple "situations" can appear: (a) a "number-theoretic function" χ that produces a single natural number, or (b) a "predicate" R that produces either {t = true, f = false}. (And, in the context of partial recursive functions Kleene later admits a third outcome: "μ = undecided".) Kleene splits his definition of the unbounded μ-operator to handle the two situations (a) and (b). For situation (b), before the predicate R(x, y) can serve in an arithmetic capacity in the product Π, its output {t, f} must first be "operated on" by its representing function χ to yield {0, 1}. And for situation (a) if one definition is to be used then the number theoretic function χ must produce zero to "satisfy" the μ-operator. With this matter settled, he demonstrates with single "Proof III" that either types (a) or (b) together with the five primitive recursive operators yield the (total) recursive functions, with this proviso for a total function: : For all parameters x, a demonstration must be provided to show that a y exists that satisfies (a) μyψ(x, y) or (b) μyR(x, y). Kleene also admits a third situation (c) that does not require the demonstration of "for all x a y exists such that ψ(x, y)." He uses this in his proof that more total recursive functions exist than can be enumerated; c.f. footnote Total function demonstration. Kleene's proof is informal and uses an example similar to the first example, but first he casts the μ-operator into a different form that uses the "product-of-terms" Π operating on function χ that yields a natural number n, which can be any natural number, and 0 in the instance when the μ-operator's test is "satisfied". :The definition recast with the Π-function: :μyyχ(y) = :*(i): π(x, y) = Πsχ(x, s) :*(ii): φ(x) = τ(π(x, y), π(x, ''y' ), y'') :*(iii): τ(''z' , 0, y) = y ;τ(u, v, w) is undefined for u = 0 or v'' > 0. This is subtle. At first glance the equations seem to be using primitive recursion. But Kleene has not provided us with a base step and an induction step of the general form: :* base step: φ(0, x) = φ(x) :* induction step: φ(0, x) = ψ(y, φ(0,x), x) To see what is going on, we first have to remind ourselves that we have assigned a parameter (a natural number) to every variable xi. Second, we do see a successor-operator at work iterating y (i.e. the ''y' ). And third, we see that the function μy yχ(y, x) is just producing instances of χ(y,x) i.e. χ(0,x), χ(1,x), ... until an instance yields 0. Fourth, when an instance χ(n, x) yields 0 it causes the middle term of τ, i.e. v = π(x, y' ) to yield 0. Finally, when the middle term v = 0, μy''yχ(y) executes line (iii) and "exits". Kleene's presentation of equations (ii) and (iii) have been exchanged to make this point that line (iii) represents an exit—an exit taken only when the search successfully finds a y to satisfy χ(y) and the middle product-term π(x, ''y' ) is 0; the operator then terminates its search with τ(z' , 0, y) = y''. : τ(π(x, y), π(x, ''y' ), y''), i.e.: :* τ(π(x, 0), π(x, 1), 0), :* τ(π(x, 1), π(x, 2), 1) :* τ(π(x, 2), π(x, 3), 2) :* τ(π(x, 3), π(x, 4), 3) :* ... until a match occurs at y=n and then: :* τ(''z' , 0, y) = τ(z' , 0, n) = n'' and the μ-operator's search is done. For the example Kleene "...consider[s] any fixed values of (xi, ..., xn) and write[s] simply 'χ(y)' for 'χ(xi, ..., xn), y)'": 1, ..., Qm are mutually exclusive predicates (or "ψ(x) shall have the value given by the first clause which applies), is primitive recursive in φ1, ..., Q1, ... Qm: :: φ(x) = ::* φ1(x) if Q1(x) is true, ::* . . . . . . . . . . . . . . . . . . . ::* φm(x) if Qm(x) is true ::* φm+1(x) otherwise Observ that the Qi are predicates -- they are defined (usually -- they could be logical operators) from the natural numbers to a single output from the truth-set { t, f }. As in the first two examples, before we can build the CASE operator from simpler primitive recursive functions we first need to apply a representing function ψi to each Qi: : ψi( Qi = t = "true" ) = 0 : ψi( Qi = f = "false" ) = 1 Then to be able to use the prf product Π and sum Σ functions in the demonstration below we will need to "flip the sense" of ψi to produce "1" when Qi is "true"; we use the prf ~sg(x) to do this -- it produces 1 if its input x is 0 and vice versa. Applying ~sg to ψ then returns "positive logic" "Qi = t => 1" and "Qi = f => 0": :* ~sg( ψi( Qi = t ) = 1 :* ~sg( ψi( Qi = f ) = 0 Given these tools, Kleene then provides us with two equivalences for the CASE function :(1) CASE φ(x) = ~sg(ψ1 ) * φ1 + . . . + ~sg(ψm ) * φm + [ ψ1 * ... * ψm * φm+1 ] :(2) CASE φ = μyy≤φ1+...+φm ( Q1 & y=φ1 ) V ... V ( Qm & y=φm ) V [ ( ~Q1 & ... & ~Qm ) & y=φm+1 ] On the right-hand side of both equations the terms in brackets [ ] are the conditions that must be met for the default or "otherwise" case. Definition (1) is just using * as a form of logical AND, and + as a kind of arithmetic OR. Definition (2) is actually using AND and OR( V ) but something subtle has appeared. In the second definition using the μ-operator: y must range over a (potentially-) large number that is the sum of the various φi, i.e. φ1 + . . . + φm. To see why this is the case, we design an example with only two cases and a default case. Substitute constants for the various φi, say φ1 = 27, φ2 = 19, φm+1 = 31: : φ(x) = :* φ1(x) = 27 if "x = 1" is true, :* φ2(x) = 19 if "x = 2" is true, :* φ3(x) = 31 otherwise Unlike definition (1), the definition (2) contains "Boolean" logic-function terms that look like this: Q1 & y=φ1. Here, before the equivalence "y=φi" can be tested, y must begin at 0 and then range successively "up" to φi, e.g. 27. If this fails because Q1 = false, then y must restart with :* Q2 & y=φ2 and proceed all the way up to φ2 = 19 before it can test to see if "x = 2". Failing this, y must restart again and proceed to 31 before it can satisfy the right-most term and declare that μyR(y) = 31. So the worst case number of steps that the μ-operator must proceed through will be (at the very worst) the sum of the steps for each case: :φ1(x) + φ2(x) + φ3(x) = 27 + 19 + 31 --> j : : { CLeaR (rj), INCrement (rj), and Jump_if_rj = rk_to_instruction Iz } --> Example 3: Definition of the unbounded μ-operator in terms of an abstract machine Both Minsky (1967) p. 21 and Boolos-Burgess-Jeffrey (2002) p. 60-61 provide definitions of the μ-operator as an abstract machine; see footnote Alternative definitions of μ. The following demonstration follows Minsky without the "peculiarity" mentioned in the footnote. The demonstration will use a "successor" counter machine model closely related to the Peano Axioms and the primitive recursive functions. The model consists of (i) a finite state machine with a TABLE of instructions and a so-called 'state register' that we will rename "the Instruction Register" (IR), (ii) a few "registers" each of which can contain only a single natural number, and (iii) an instruction set of four "commands" described in the following table: :In the following, the symbolism " [ r ] " means "the contents of", and " →r " indicates an action with respect to register r. 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+3)rd 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. == See also ==