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$?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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)$$
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$$
it reduces to itself in an infinite loop.