Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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!

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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,

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.