# Looping (ω) Combinator

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$?

-

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.

-
Thanks! That was an great explanation of what I was misunderstanding. – J.R. Garcia Jan 3 '12 at 21:02
I think you mean "you can apply it to the identity"? – joriki Jan 3 '12 at 21:06
@joriki, corrected. Thanks. – user16697 Jan 4 '12 at 7:13