Can someone explain this combinator? I understand $\lambda x. x$, but I don't understand $\lambda x. x x$ From what I've gathered, this means given x, return the application of x to x. I don't understand the application of x to itself part. For example, given $x = 2 + y$, would $\lambda x. x x$ result in $y^2 + 4y + 2$?
Looping (ω) Combinator
3
$\begingroup$
lambda-calculus
combinatory-logic
1 Answers
10
2 + y is a number, not a lambda calculus term so you cannot use that here.
you can apply it to the identity and it will reduce like this:
$(\lambda x. x x) (\lambda y. y) \to (\lambda y. y)(\lambda y. y) \to (\lambda y. y)$
rewritten in terms of combinators this is: $\omega I \to II \to I$
notice what happens if you apply it to itself?
$(\lambda x. x x) (\lambda x. x x) \to (\lambda x. x x)(\lambda x. x x) \to \ldots$
rewritten in terms of combinators this is: $\omega \omega \to \omega \omega \to \ldots$
it reduces to itself in an infinite loop.
-
0@joriki, corrected. Thanks. – 2012-01-04