Can any one please help:

Attachment 22313

Printable View

- Sep 18th 2011, 06:24 PMsureshciscoLambda Conversion (alpha and beta conversion)
Can any one please help:

Attachment 22313

- Sep 19th 2011, 03:12 AMemakarovRe: Lambda Conversion (alpha and beta conversion)
Alpha-conversion needs to be performed to avoid variable capture. This happens when reducing $\displaystyle (\lambda x.\,M)N$ and the term N has some free variable y that would become bound if N is substituted for x in M because there is a $\displaystyle \lambda y$ somewhere inside M. To avoid capture of y, $\displaystyle \lambda y$ in M has to be renamed into some $\displaystyle \lambda z$. For example, in problem (a), x would be captured if substituted for y in $\displaystyle \lambda x.\,xy$, so this bound x has to be renamed.

Consider problem (b). I'll omit some parentheses and will write $\displaystyle \lambda xy$ for $\displaystyle \lambda x\lambda y$.

$\displaystyle (\lambda xy.\,x(\lambda x.\,xy))(\lambda xy.\,yx)$ -> (substituting $\displaystyle (\lambda xy.\,yx)$ for x)

$\displaystyle \lambda y.\,(\lambda xy.\,yx)(\lambda x.\,xy)$ -> (need to rename y because the argument has y free)

$\displaystyle \lambda y.\,(\lambda xz.\,zx)(\lambda x.\,xy)$ -> (substituting $\displaystyle (\lambda x.\,xy)$ for x)

$\displaystyle \lambda yz.\,z(\lambda x.\,xy)$