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.

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. " (\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 ACA 0 when combined with the usual base theory of higher-order reverse mathematics. Π s≤t f s (x, s) = f 0 (x, 0) × f 1 (x, 1) × ... × f t (x, t) Σ t g t (x, t) = g 0 (x, 0) + g 1 (x, 1) + ... + g z-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): "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: μy y χ(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 x i . 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 (x i , ..., x n ) and write[s] simply 'χ(y)' for 'χ(x i , ..., x n ), y)'": For an example of what this means in practice see the examples at General recursive function—even the simplest truncated subtraction algorithm "x - y = d" can yield, for the undefined cases when x j , r k , z) } The unbounded μ-operator is also defined by Boolos-Burgess-Jeffrey (2002) p. 60-61 for a counter machine with an instruction set equivalent to the following: { CLR (r), INC (r), DEC (r), JZ (r, z), H } In this version the counter "y" is called "r2", and the function f( x, r2 ) deposits its number in register "r3". Perhaps the reason Boolos-Burgess-Jeffrey clear r3 is to facilitate an unconditional jump to loop; this is often done by use of a dedicated register "0" that contains "0":

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353547916 under CC BY-SA 4.0; modifications have been made.