# Lambda Conversion (alpha and beta conversion)

• Sep 18th 2011, 06:24 PM
sureshcisco
Lambda Conversion (alpha and beta conversion)

Attachment 22313
• Sep 19th 2011, 03:12 AM
emakarov
Re: Lambda Conversion (alpha and beta conversion)
Alpha-conversion needs to be performed to avoid variable capture. This happens when reducing $(\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 $\lambda y$ somewhere inside M. To avoid capture of y, $\lambda y$ in M has to be renamed into some $\lambda z$. For example, in problem (a), x would be captured if substituted for y in $\lambda x.\,xy$, so this bound x has to be renamed.

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

$(\lambda xy.\,x(\lambda x.\,xy))(\lambda xy.\,yx)$ -> (substituting $(\lambda xy.\,yx)$ for x)
$\lambda y.\,(\lambda xy.\,yx)(\lambda x.\,xy)$ -> (need to rename y because the argument has y free)
$\lambda y.\,(\lambda xz.\,zx)(\lambda x.\,xy)$ -> (substituting $(\lambda x.\,xy)$ for x)
$\lambda yz.\,z(\lambda x.\,xy)$