3
$\begingroup$

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

1 Answers 1

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