Lambda Calculus reduction

user_183717 0
Viewed 10564

All,

Below is the lambda expression which I am finding difficult to reduce i.e. I am not able to understand how to go about this problem.

(λm λn λa λb . m (n a b) b) (λ f x. x) (λ f x. f x)

This is what I tried, but I am stuck:

Considering the above expression as : (λm.E) M equates to
E= (λn λa λb. m (n a b) b)
M = (λf x. x)(λ f x. f x)

=> (λn λa λb. (λ f x. x) (λ f x. f x) (n a b) b)

Considering the above expression as (λn. E)M equates to
E = (λa λb. (λ f x. x) (λ f x. f x) (n a b) b)
M = ??

.. and I am lost!!

Can anyone please help me understand that, for ANY lambda calculus expression, what should be the steps to perform reduction?

reduction lambda-calculus lambda
3 Answers

Just substitute a thing for its corresponding thing:

(λm λn λa λb . m          (n            a b) b) (λ f x. x) (λ f x. f x)
= ~            ^________                        ~~~~~~~~~~
   (λn λa λb . (λ f x. x) (n            a b) b)            (λ f x. f x)
=    ~                     ^__________                     ~~~~~~~~~~~~
      (λa λb . (λ f x. x) ((λ f x. f x) a b) b)
=                 ~       ~~~~~~~~~~~~~~~~~~
      (λa λb .   (λ x. x)                    b)
=                   ~  ^                     ~
      (λa λb .         b                      )

That is all.

user_8498910
Related