Talk:Mu operator

From Wikipedia, the free encyclopedia

"if and only if

   f(z) = 0 and
   for every y < z, f(y) is defined and f(y) > 0. "

Surely f(y) may be negative (Since it is a map from positive integers to integers). So shouldn't it be:

"if and only if

   f(z) = 0 and
   for every y < z, f(y) is defined and f(y) != 0. "

But I might be missing something so I shall not edit it myself. Anyone else?

Contents 1 Undo rename 2 Edit of 2006-9-22 3 Modal mu calculus 4 Holding place: motivation for the mu-operator

[edit] Undo rename

As far as I can tell, this page should be named mu operator according to WP:NAME; non ASCII titles are not permitted. Otherwise, I would have renamed it myself a month ago. Although the software accepts non ASCII titles, it does not handle them correctly; see Category:Recursion theory. Moreover, non ASCII titles are apparently not permitted by policy. I hope that there is an easy way for some administrator to undo the renaming etc. CMummert 02:15, 19 August 2006 (UTC)

• I agree with this: the new title would violate policy WP:ENGLISH in the sense that titles should contain characters from the Latin alphabet only, but μ is from the Greek alphabet. I also discovered that the page on the modal mu calculus was titled Modal μ calculus, so I requested a page move to Modal mu calculus. -- eboy 10:47, 11 October 2006 (UTC)

[edit] Edit of 2006-9-22

The information added by WVBailey today is very pertinent, but I think it should be integrated into the body of the article rather than put in the references.

Also, it can't be true that a conditional expression with a primitive recursive predicate is equivalent to the minimization operation, because if P,Q,R are primitive recursive then so is the function defined to be R if P is nonzero and Q otherwise. I haven't looked at Minsky's book, but either it is wrong or the interpretation here is. So I moved the following from the article to here.

Minsky introduces the "McCarthy Formalism" that reduces the μ-operator to a conditional if-then formulation: "McCarthy introduces 'conditional expressions" of the form

"f = if p₁ then e₁ else e₂ )

"where the e_i are expressions and p₁ is a statement (or equation) that may be true or false...This conditional expression... has also the power of the minimization operator. ...The MacCarthy formalism is like the general recursive (Kleene) system, in being based on some basic functions, composition, and equality, but with the conditional expression alone replacing both the primitive-recursive scheme and the minimization operator." (boldface in original, p. 193).

CMummert 15:15, 22 September 2006 (UTC)

---

Entirely possible that I got the interpretation wrong. Here's some more. In a footnote (p. 193) to the above Minsky states:

'Note that we cannot regard (if p then a else b) as simply a function of three quantities p, a, and b. For this would make us evaluate them all beforehand. But, often, the computation of b will never terminate when p is true; in this case we must evaluate a without even looking at b.

Later (p. 210) he shows how to concoct the u-operator from his register machine (also cf register machine models). He presupposes that φ(t) is primitive recursive. Starting from "t =zero" his routine that he labels [μ_i] just evaluates function φ(t) until the function returns "0" in register φ:

"the least t for which φ(t) = 0" (p. 210)

(He has to clear register w to zero to facilitate the conditional jump.) In the following, both t and w are registers. We are assuming that routine φ(t) is returning its value in register φ:

[μ_i] =

• CLEAR w
• CLEAR t

loop:

• DO φ(t)

; the primitive recursive function routine in instructions { CLEAR r, INCREMENT r, IF ri ≠ rj THEN jump-to xxx }

• INCREMENT t
• IF φ ≠ w THEN GOTO loop

;remember, here w = 0

*INCREMENT t

*etc.

In the following pages (if I understand this) Minsky then shows how to create a register machine using unbounded repeats. He uses the repeat so it does not include itself "within its range". He then advances to the general recursion case where the repeat does include itself.

"The outstanding feature that distingishes primitive recursion is that one knows in advance (by the value of y) how many times the iteration (of a primitive-recursive scheme) will have to be done. For general recursion, with the u-operator, one doesn't usually know this until after the work is done and computation terminated." (p. 212, italics in original).

BUT .. he ends up his discussion with the very salient observation that, in general, with the register machine model he has a problem because the finite instructions cannot accommodate (a possibly huge number resulting from) a quasi-unbounded repeat. (Minsky is not entirely clear here. The only way I can understand this stuff is to actually build the models in Excel and run them. I built the example on p. 210. But then the chi's and phi's began to appear ... thus I fell into this "recursion" stuff.)

There is a demonstration in Melzak (1961) of Melzak's pebble/register model where he tackles his model's Turing equivalence but only after creating an "indirect" instruction using his unbounded registers cf Register machine models.

As I read what I wrote above, there may be an issue. Minsky (1967) doesn't cite Melzak (1961). Maybe you touched on it. My head is twirling... wvbaileyWvbailey 19:02, 22 September 2006 (UTC)

I don't have Minsky's book, but I will see if it is in the library the next time I am there. CMummert 19:45, 22 September 2006 (UTC)

[edit] Modal mu calculus

User:Duja merged modal mu calculus here. I'm not convinced that this article on the mu operator (which is not about the mu calculus, only about the recursion-theoretic operator) is the right place for that material. Duja also merged mu calculus here. Unless there are strong objections, I will undo the merge soon. I think the right thing is to have an article on mu calculus, and include the material on modal mu calculus there. But I have no desire (or expertise) to write the article on mu calculus. CMummert 16:30, 24 October 2006 (UTC)

I am in favour of undoing the merge. I think your proposed title mu calculus is the best option. If I can find the time, I'll try to expand on the article. eboy 18:20, 24 October 2006 (UTC)

I merged it as admin closing the RM; you're welcome to undo the merge, but my sole intention was to merge a substub into a (seemingly) appropriate article. While mu calculus article seems desirable indeed, it looks fairly pointless to revert it to the previous state, which was basically empty. IOW, the merge is certainly not the right thing to do in the long run, but unless at least something there is expanded (and it seems there is no one knowledgeable enough to do it at the moment), IMO it's better to have a redirect than a contextless sentence. If you want to move it to mu calculus, just ping me. Duja 06:49, 25 October 2006 (UTC)

Duja, I agree with you that the article is a substub. If you like, I can add a few sentences making into a normal stub. But the way it is now (defined in the external links section of the mu operator) is worse than it already was. Shall I move the content on the mu calculus to the mu calculus page and add some content? eboy 09:34, 25 October 2006 (UTC)

Lemme do that so that edit histories are preserved. I'll get back in a minute. Duja 09:47, 25 October 2006 (UTC)

Done. mu calculus is now the old stub. Duja 09:51, 25 October 2006 (UTC)

Thank you, Duja. eboy 10:05, 25 October 2006 (UTC)

BTW Shouldn't the wrong title template on top of the mu operator page be removed? According to policy WP:ENGLISH, the current title is correct. eboy 10:11, 25 October 2006 (UTC)

Hmm. IMO WP:ENGLISH doesn't apply as such; it really depends on whether eminent matematical literature refers to it as "μ operator/calculus" or "mu uperator/calculus". Offhand, I'd say the former, thus {{wrongtitle}} applies. Duja

But the article starts by saying that article titles should use the Latin alphabet, and the Greek letter μ is not part of that. Why shouldn't this apply then? eboy 12:27, 25 October 2006 (UTC)

The point of the wrongtitle template is for titles that are correct per WP:ENGLISH but wrong per the real world. The reason for the wrongtitle template here is exactly that WP:ENGLISH requires the actual title to be anglicized, but in any other setting the Greek letter should be used instead of the anglicized version. There was some recent iscussion within the Math project about math articles with Greek letters in their names, and there is not complete consensus on how to deal with them. CMummert 12:38, 25 October 2006 (UTC)

[edit] Holding place: motivation for the mu-operator

The following is CMummert's explanation for the reason why the mu-operator is necessary if one wants to generate the partial recursive functions. wvbailey has added some subscripted numbers etc.:

The motivation for the mu operator is this. Suppose that you have the ability to effectively determine whether a natural number a_i is in a particular set A:

A = { a₁, ... a_i, .... a_?, .... }

And suppose furthermore that you have an effective function f such that you can prove that if you start with any number n and successively compute f(n), f(f(n)), f(f(f(n))), and so on, eventually you will find a number in A, i.e.

f( ... f( f( f(n) ) ) ... )^{do q times} = a_?,

Define a function g that takes input n and returns the first number in A that can be found by iteratively applying f:

g(n, set A, f(n), t) = g(n, { a₁, ... a_i, ... a_?, .... } → t_{first ai ε A}

ε means "element of the set"

t is a counter that starts from 0 and increments up each time f( ) occurs; t represents the number of times f is iterated

Then g should be effective as well. This follows from the Church-Turing thesis: since I told you a mechanical procedure for finding g(n), the function g should be Turing computable. And, if if you read "effective" to mean "computable" then this is correct - g will be a computable function if A is decidable and f is a computable function. But even if f is a primitive recursive function and A is a primitive recursively decidable set, g may not be primitive recursive. The problem is that although you know that for each n you will eventually find g(n), you don't know how many iterations t_? are required.

So the function h(n,t) which applies f to n iteratively for t iterations will be primitive recursive if f is. The definition of h is

h(n,0) = n

h(n,t+1) = f(h(n,t))

But the function g is definable as but not generally definable as a primitive recursive fuction (without the mu operator). So if you are interested in having a syntactic definition for every computable function, you need the mu operator as well as the syntax used to define primitive recursive functions. It's essentially just a programming language in which the mu operator is used to construct loops.

---

This is from Minsky (1967) where he uses the McCarthy Formalism to provide the base functions for the partial recursive functions:

μ(x, N) =_def (if f(x) = N then x else μ(x',N))" (p. 192)

i.e.

μ(x, N) = ( if f(x) = N then x else μ(x+1,N))

>Insert table here

> Example from §57 The u-operator, enumeration, diagonal procedure. Here, no bound on the iterating-number y ("unbounded search operator"): Kleene (1952) p. 280:

Kleene recasts the mu-operator in terms of the "product operator Π" as follows: (VI'): here use x in place of the nasty mess "x₁, ... x_n" and Kleene used z' rather than z+1 and y'rather than y+1:

φ(x) = μy[ χ(x,y) = 0 ] =_def

π(x,s)= Π_s<yχ(x, s)

τ(z+1, 0, y) = y

φ(x) = τ( π( x,y ), π( x,y+1 ), y )

Example: let y = 3 from table below: ??

φ = τ( π(3), π(4), 3) = 3

	y=0	y=1	y=2	y=3	y=4	y=5	y=.......
χ(y)	3	1	2	0	9	0	. . . .
π(y)= Πs<yχ(s)	1	3	3	6	0	0	. . . .
s<y	---	0	0, 1	0, 1, 2	0, 1, 2, 3	0, 1, 2, 3, 4	. . . .
χ(s)	χ(0)=3	χ(1)=1	χ(2)=2	χ(3)=3	χ(4)=9	χ(5)=0	0
Πs<yχ(s)	---	χ(0) =3	χ(0)*χ(1) =3*1=3	χ(0)*χ(1)*χ(2) =3*1*2=6	χ(0)*χ(1)*χ(2)*χ(3) =3*1*2*0 = 0	0	0

χ ψ Ψ ψ φ τ Χ μ ≤ ≥ ≠

Better example:

In Kleene's proof that the CASE( , ... , ) operator is a primitive recusive function (p.r.f) Kleene provides two versions of the proof. The first uses (i) "representing functions" for "the predicates Q", (ii) the ~sgn( ) p.r.f., (iii) and an "arithmetic calculation" in to derive the CASE operator. The second one uses a bounded mu-operator operating over a string of OR(Q_i & "y=φ_i"). The two proofs result in the equivalent value for "φ", one searching in sequence (the mu-version) the other just doing the search "in parallel". The resulting output-value "φ" has to be the mu's value for its y, because "y=φi". This just (seems to) mean that:

Hypothesis: The bounded mu-operator for predicates is identical to the CASE operator.

Definition of a predicate Q_k: it has a truth value of { true "t", false "f" }.

The predicates Q₁, ... Q_m used in the definition of the “case” primitive recursive function must be “mutually exclusive” – only one of these predicates can be true at a time; the rest must be false.

Definition of a representing function of a predicate:

If the truth value of predicate Q_i is "true" then its representing function ψ_i has a value of 0 [!]; if the truth value of Q_i = "false" then its representing function ψ_i = 1 [!]

Definition of the ~sgn( ) function is similarly “backwards”: ~sgn(a)= 1 if a=0 and vise versa.

So: ~sgn(ψ(Q)_k)= 1 if Q_k="true" and 0 if false.

In the “case functions” we omit the messy x = (x₁, . .. , x_m):

An approximate natural language form:

CASE( Q(x),φ(x) ) = φ =

φ₁ if Q₁ = "true" OR ... OR φ_m if Q_m = "true" OR φ_m+1 otherwise i.e. all the Q_i are false.

Kleene's first proof CASE is a p.r.f. without using the mu-operator:

CASE( ψ(x),φ(x) ) = φ =

~sg(ψ(Q)₁)*φ₁ + . . . + ~sg(ψ(Q)_m)*φ_m *[ ψ(Q)₁* . . .*ψ(Q)_m ]*φ_m+1

Rewrite φ in quasi-natural language, simpler terms of the predicates Q:

CASE( Q(x),φ(x) ) = "φ" =

[ Q₁ => t:1 or f:0]*φ₁ + . . . +[ Q_m => t:1 or f:0]*φ_m +[ Q₁ => t:1 or f:0]* . . .* [ Q_m) => t:1 or f:0]*φ_m+1

Kleene's second proof that CASE is a p.r.f. using the mu-operator:

CASE( Q(x),φ(x) ) ="φ" = y = μy_{y≤φ1+...+φm+1} {(Q₁ & y=φ₁) V . . . V(Q_m & y=φ_m) V (~Qm & . . . & ~Qm & y=φ_m+1) }

Since these are equivalent φ we can equate the two versions and see what we get – #2 is the “serial, iterative” version and #1 is the “parallel-"all-at-once version. To make "easier" to see what is happening:

Σφ =_def φ₁ + ... +φ_m+1,

summation Σ_i=1^i=Σφ, product Π_i=1^i=m, serial OR V_i=1^i=m, serial AND &_i=1^i=Σ

Equate the "φ" from both proofs:

CASE( Q(x),φ(x) )= "φ" = y =

μy_y≤Σφ { V_i=1^i=Σφ (Q_i & y=φ_i) V [ &_i=1^i=m (~Qi) & y=φ_m+1 ] }

= Σ_i=1^i=m [ (Q_i => t:1 or f:0 )*φ_i ] + [ Π_i=1^i=m ( Q_i => t:1 or f:0 ) ]*φ_m+1

Conclusion: The bounded mu-operator (for predicates) and the CASE operator seem to be functionally identical. The above does seem to agree with Kleene's "recasting" of his (VI) into (VI') for his proof of "Theorem III". So this means that Minsky and McCarthy are right -- the "IF-THEN-ELSE" = CASE( ) plus successor plus "equality of numbers y=φ_i, the "i" iterated and the various "CASEs" selected and compared, seems to generate a mu-operator:

φ(x) = τ( π( x,y ), π( x,y+1 ), y ) = y

wvbaileyWvbailey 21:39, 29 October 2006 (UTC)