CODEWITHSUNDEEP
lambdalambda-calculusreduction
Priit
Priit

Reputation: 1

How do parentheses work in Lambda Calculus Reduction?

Okay so I'm just learning some lambda calculus and I came across this problem.

Perform reduction on this - if it cannot be reduced then say it will diverge (λy.(λx.xx)y)(λx.x)

These are the steps I tried following.

(λy.(λx.xx)y)(λx.x) [1]
(λy.(xx)[x:=y])(λx.x) [2] Beta Reduction
(λy.yy)(λx.x) [2]
(yy)[y:=λx.x] [3] Beta Reduction
(λx.x)(λx.x) [3]
(λx.x)(λx'.x')[4] Alpha Reduction
(x)[x:=λx'.x')[5] Beta Reduction
(λx'.x')[6] Final Reduction.

I've then tried to confirm my answer using a calculator online and apparently the final answer should be.

= xx

The steps they took were:

(λy.(λx.xx)y)(λx.x)
(λy.xx)(λx'.x') - Beta Reduction
xx - Beta Reduction

If somebody could let me know where I went wrong I'd appreciate it!

Upvotes: 0

Views: 82

Answers (1)

Will Ness
Will Ness

Reputation: 71070

You didn't go wrong. Your result is correct:

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

Upvotes: 0

Related Questions