1
$\begingroup$
  1. In recursion for λ calculus, I was wondering why the following two are equal

    (λx.g (x x)) (λx.g (x x))

    g ((λx.g (x x)) (λx.g (x x)))

  2. How shall I understand g ((λx.g (x x)) (λx.g (x x)))?

I am learning λ calculus from Wikipedia, and I can understand many of its basics.

Thanks!

1 Answers 1

3

When you evaluate $(\lambda x.g(x x)) (y)$, it is equivalent to $g(y y)$ (This is called $\beta$-reduction). Therefore, when you do $ (\lambda \, x.g(x \, x))(\lambda \, x.g(x \, x)) $ You can see the second parenthesis as the "big chunk you're putting as an argument in your abstraction on the left", so that $ (\lambda \, x.g(x \, x))(\, Y \,) \quad \underset{\beta}{\rightarrow} \quad g(\,Y \quad Y\,) \quad \rightarrow \quad g( (\lambda \, x.g(x\, x)) (\lambda\, x.g(x \,x)) ) $ (I used the right-arrow to say "reads as". This is standard for $\beta$-reduction.)

Wikipedia is not a place to learn, it's a reference. You should use it only to take a look at fun stuff or recall something you've already learned. For learning, you should use books or tutorials, it's a better idea. Try this as a tutorial : http://classes.soe.ucsc.edu/cmps112/Spring03/readings/lambdacalculus/introduction.html

Hope that helps,