Lambda calculus Beta reduction

130 Views Asked by At

When applying Beta reduction does the function also affect on the $\lambda$ term? (If same value)

For example

$\lambda$ z.$\lambda$ z (z z) t

What is the correct reduction?

$\lambda$z (t t) or

$\lambda$t (t t)

1

There are 1 best solutions below

0
On

The beta contraction of $(\lambda x . M)\, N$ is defined as $[N/x]\, M$, and recall that the substitution is done by replacing every free instance of $x$ by $N$.

Explicitly, $(\lambda z. (\lambda z. zz))t \triangleright_\beta [t/z]\,(\lambda z. zz)$, but as there is no free occurence of $z$ no substitution is performed.