Talk:Μ operator

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

"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

[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)

[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 p1 then e1 else e2 )
"where the ei are expressions and p1 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 ai is in a particular set A:
A = { a1, ... ai, .... 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, { a1, ... ai, ... a?, .... } → tfirst 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 h(n, \mu t\,[h(n,t) \in A]) 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 "x1, ... xn" 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(Qi & "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 Qk: it has a truth value of { true "t", false "f" }.

The predicates Q1, ... Qm 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 Qi is "true" then its representing function ψi has a value of 0 [!]; if the truth value of Qi = "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 Qk="true" and 0 if false.

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

An approximate natural language form:

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

φ1 if Q1 = "true" OR ... OR φm if Qm = "true" OR φm+1 otherwise i.e. all the Qi are false.

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

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

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

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

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

[ Q1 => t:1 or f:0]*φ1 + . . . +[ Qm => t:1 or f:0]*φm +[ Q1 => t:1 or f:0]* . . .* [ Qm) => 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 = μyy≤φ1+...+φm+1 {(Q1 & y=φ1) V . . . V(Qm & 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 φ1 + ... +φm+1,
summation Σi=1i=Σφ, product Πi=1i=m, serial OR Vi=1i=m, serial AND &i=1i=Σ

Equate the "φ" from both proofs:

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

μyy≤Σφ { Vi=1i=Σφ (Qi & y=φi) V [ &i=1i=m (~Qi) & y=φm+1 ] }

= Σi=1i=m [ (Qi => t:1 or f:0 )*φi ] + [ Πi=1i=m ( Qi => 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)

[edit] Naming

Could we agree on a name to use in the article? In the first section it's called mu operator and in the rest of the article it's called μ operator. Then there's the entire thing with the title. First it different from the majority spelling used in the article. Second forwhateverreason somebody thought it should be called μ operator and simply stuck {{wrongtitle}} without moving the page. --Dispenser 07:53, 29 December 2006 (UTC)

Support for lowercase-first-letter was added as a hack only recently to Wikimedia software, and the article didn't follow suit (see μTorrent as a counterexample). I'd endorse the move to μ operator. Better still, I'll be bold and move it. Duja► 08:37, 29 December 2006 (UTC)
Notice, though, that the only place where the article title is correct is the article itself (because the "fix" is just a hack) — it will still be displayed with uppercase Mu on Talk, History, Watchlist, Category etc. Duja► 08:53, 29 December 2006 (UTC)

[edit] Merge

Should the article mu-recursive function be merged with this article? I think this article has the better title (ignoring issues of latin versus greek) since the class of mu-recursive functions already has its own page at computable function. --Quux0r 02:22, 11 April 2007 (UTC)

To keep the discussion in one place, please comment at Talk:Μ-recursive function. CMummert · talk 02:23, 11 April 2007 (UTC)

[edit] Not Helpful

This page isn't at all helpful in explaining the idea of 'Effective Minimum' to me. Where are the examples? It really reads like it's written for experts by experts. —Preceding unsigned comment added by Myrikhan (talk • contribs) 18:00, 3 April 2008 (UTC)