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)))
- 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!
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,