Lambda Calculus: What is the difference between a $\lambda$ term with and w/o parenthesis?

33 Views Asked by At

Eg. what is the difference between $(\lambda y.M)[x:=N]$ and $\lambda y.M[x:=N]$?

1

There are 1 best solutions below

0
On BEST ANSWER

The substitution applies to the whole expression in the first term.

The substitution only applies to M in the second term.

In this case the two are equal. If you had $(\lambda x.M)[x:=N]$ they would not be equal any longer as the substitution would end rather than recursively work inside the body of the lambda.