3

I've came across an example and I'm not quite sure on how the solution was met after performing beta-reduction on the following expression. It doesn't show any of the steps. Any help is appreciated!

(x. (y. y)) (a. (b.a))

(y. y)

bldzrr
  • 51

1 Answers1

2

The $(\beta)$ rule tells us that an expression of the form $(\lambda x . s)t$ reduces to $s[t/x]$.

In your case we have $t \equiv (\lambda a .(\lambda b. a))$, and $s \equiv \lambda y . y$.

Then one $\beta$-reduction gives us $s[t/x]$, which is just equivalent to $s$ because $x$ doesn't appear free in $s$.

Daniel Mroz
  • 2,346