CODEWITHSUNDEEP
lambdalambda-calculus
JAN
JAN

Reputation: 21865

Find a normal form using beta reduction

Given the following expression : 

((λx.λx.xx) (λx.xzx)) (λy.yy)

I want to find its normal form using beta reduction.

My calculation : 

((λx.λx.xx) (λx.xzx)) (λy.yy) ->
((λx.xzx)(λx.xzx)) (λy.yy) -> ((λx.xzx)z(λx.xzx)) (λy.yy) ->
(zzz (λx.xzx)) (λy.yy) -> ?

But how can I continue from here : 

(zzz (λx.xzx)) (λy.yy) -> ?

Thanks

Upvotes: 1

Views: 1835

Answers (1)

Rubens
Rubens

Reputation: 14778

Using \ to represent λ:

((\x.\x.xx) (\x.xzx)) (\y.yy) =
= ((*\x*.\x.xx) *(\x.xzx)*) (\y.yy) =
= (\x.( (\x.xzx) (\x.xzx) )) (\y.yy) =
= (\x.( (*\x*.xzx) *(\x.xzx)* )) (\y.yy) =
= (\x.( (\x.xzx) z (\x.xzx) )) (\y.yy) =
= (\x.( ( (\x.xzx) z) (\x.xzx) )) (\y.yy) =
= (\x.( ( (*\x*.xzx) *z*) (\x.xzx) )) (\y.yy) =
= (\x.( ( (zzz) (\x.xzx) ) (\y.yy) =
= (*\x*.( ( (zzz) *(\x.xzx)* ) (\y.yy) =
= (zzz) (\x.( (\y.yy) z (\y.yy) )) =
= (zzz) (\x.( ((\y.yy) z) (\y.yy) )) =
= (zzz) (\x.( ((*\y*.yy) *z*) (\y.yy) )) =
= (zzz) (\x.( (zz) (\y.yy) )) =
= (zzz) (\x.(zz)(\y.yy))

And there's no further application available here -- at least, as long as you don't have definitions for z.

Notice, also, that there is an x definition in the final expansion, which you might've suppressed during your calculations.

All the variables (λx . λx . xx) have in common in the expression:

((*λx*.*λx*.xx) (λx.xzx)) (λy.yy)

are their names. They're different variables nonetheless.

Upvotes: 1

Related Questions