The bounded μ-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 and w ≤ y ≤ z.
The total version of the unbounded μ-operator is studied in higher-order reverse mathematics (Kohlenbach (2005)) in the following form:
This axiom gives rise to the Big Five system ACA0 when combined with the usual base theory of higher-order reverse mathematics.
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).
is coming from the output of R: Kleene demonstrates that μyy 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. (And, in the context of partial recursive functions Kleene later admits a third outcome: "μ = undecided". 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: Kleene also admits a third situation (c) that does not require the demonstration of "for all x a y exists such that ψ(x, y)." 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 u-operator's test is "satisfied". Finally, when the middle term v = 0, μyy 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. 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: 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). 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. What is mandatory if the function is to be a total function is a demonstration by some other method (e.g. induction) that for each and every combination of values of its parameters xi some natural number y will satisfy the μ-operator so that the algorithm that represents the calculation can terminate: For an example of what this means in practice see the examples at mu recursive functions—even the simplest truncated subtraction algorithm "x - y = d" can yield, for the undefined cases when x < y, (1) no termination, (2) no numbers (i.e. something wrong with the format so the yield is not considered a natural number), or (3) deceit: wrong numbers in the correct format. The "proper" subtraction algorithm requires careful attention to all the "cases" But even when the algorithm has been shown to produce the expected output in the instances {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, we are left with an uneasy feeling until we can devise a "convincing demonstration" that the cases (x, y) = (n, m) all yield the expected results. In the usual μ definition register w will contain 0, but Minsky observes that it can contain any number k. Minsky's instruction set is equivalent to the following where "JNE" = Jump to z if Not Equal: 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: 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":