How to reduce these equations with beta reduction - lambda calculus

307 Views Asked by At

How do I beta reduce these equations. My attempts are below the questions.

  1. (λy.zy)a

= λy[y:=a].zy

= λa.za

  1. (λz . zz)(λy . yy)

= λz[z:=λy . yy].z z

= (λy . yy)(λy . yy)

= (λy[y:=λy . yy].yy)

= (λy . yy)y

= λy[y:=y]y

  1. (λx.x)(λx.x)

= (λx[x:=λx.x].x)

= λx.x

  1. (λx.xy)(λx.xx)

= (λx[x:=λx.xx].xy)

= (λx.xx)y

= λx[x:=y].xx

= yy

Are my solutions correct?

1

There are 1 best solutions below

2
On BEST ANSWER
  1. After substituting $[y:=a]$, the leading $\lambda$ should be resolved (omitted), so we get $za$.
  2. Let $s:=\lambda y. yy$. After the first step, when you arrived to $ss$, I can't follow you. When applying the $\beta$-reduction to $ss$, we get back $ss$ again.
  3. and 4. are correct.