Talk:Fixed-point combinator

Klop combinator

Did anybody notice that the fixed point combinator by Klop as given here is wrong? Did anybody actually try it? I used it to test my lambda-calculus interpreter and I was thinking of a bug in it, until I found the correct definition somewhere on the web: [1] (look for $). There should be 26 L's, not 28 as given here. The problem is that many web pages directly copy from the Wikipedia text, and give the same (wrong) definition. I don't know whether the page was vandalized long ago, or it was a genuine transcription error. Fixed. --positron 10:14, 7 March 2006 (UTC)[reply]

I don't think anybody did try it. Should've just removed it when I did a big cleanup a while back, I suppose. Thanks for the fix. —donhalcon^╤ 14:52, 7 March 2006 (UTC)[reply]

Dumbing Down

Could you dumb it down a shade? --Mike Schiraldi 01:53, 27 Jun 2005 (UTC)

I think the first paragraoh is misleading the reader into thinking about fixpoints as real values, whereas the following paragraph is talking about a fixpoint in function space. It takes a bit of a conceptual leap to understand the latter, and the first paragraph doesn't particularly help...

I've submitted a rewrite that should be a lot easier to understand. --bmills 18:00, 21 October 2005 (UTC)[reply]

I suspect that some of that stuff is graffiti, but I'm not expert enough to say for sure. Will someone please check on it? --unknown

Y Combinator

It seems like the Y Combinator should have its own page.

Example

Why does the example mix (a b (c d)) and a(b)(c(d)) notation? It would be a lot clearer, I think, if it stuck to (a b (c d)), and put ( ) on the lambdas as well. It would also be nice to state the final result (fact = (fix ...)). Shinobu 06:57, 8 November 2006 (UTC)[reply]

The example also appears to be wrong. It uses just part of the church numeral, and confusingly uses f to mean two different things. Can anyone confirm this? (New guy, reluctant to change/break anything) CarpeCerevisi 11:46, 8 February 2007 (UTC)[reply]

Huh?

Note that the Y combinator is intended for the call-by-name evaluation strategy, since (Y g) diverges (for any g) in call-by-value settings

Can somebody explain this? What does call-by-name versus call-by-value even mean in the context of lambda calculus? Isn't call-by-name always the case in lambda calculus? Why does Y g diverge in call-by-value? What does 'diverge' mean in this context? All these things are totally non-obvious. JulesH 19:12, 11 November 2007 (UTC)[reply]

Also, the "Example" section refers to something described as the "fix" operator, which hasn't been defined. JulesH 19:25, 11 November 2007 (UTC)[reply]

I don't get it

I've read this definition a zillion times and it still makes no sense to me.

A fixed point of a function f is a value x such that f(x) = x.

If you've got an arbitrary function f, why should there be *any* guarantee at all that it will have a fixed point in the first place? If my function is: 'f(x) = x+1', then it's never going to have a value such that f(x) = x for any integer x. If I have a higher-order function 'f(x) = x x', then that's still no guarantee that x x == x for all x's.

It seems like nonsense. What am I misunderstanding here?

I can understand a function which *creates* a higher-order function which is guaranteed to have a known fixed point -- but not one that takes an arbitrary Turing-complete function, somehow analyses it (how do you look inside a lambda abstraction in the first place when the only operation you have is application? And wouldn't working out what value it returns for all arguments involve solving the halting problem?), determines that it has a fixed point, and returns the *fixed point itself*.

Obviously this is a hugely fundamental result in basic computer science, so it must be right, and I thought I vaguely understood lambda calculus, but I can't make head or tail of this definition as written. --Natecull (talk) 23:12, 17 November 2008 (UTC)[reply]