0

Could you explain what should I do about

λx.λy.x

part? Thanks.

jason
  • 119
  • Are the numbers encoded in the standard way in $\lambda$-calculus ? If yes, $\lambda x.\lambda y.x$ is $0$. – Denis May 30 '13 at 10:35
  • also it seems that you got your parenthesis wrong, since y appears later, it is probably in the scope of the first $\lambda y$. – Denis May 30 '13 at 10:38
  • I'm guessing the plus binds tighter, so $\lambda x.\lambda y.x$ is not an individual part. – Samuel May 30 '13 at 10:38
  • @dkuper paranthesis should be true. – jason May 30 '13 at 10:39
  • if the parenthesis are true, then you have a $y$ floating in your formula, so it does not evaluate to a number. Or as @Samuel says, the + binds tighter, but it is not not standard so parenthesis should be put to avoid ambiguity. – Denis May 30 '13 at 10:44
  • and the least we can say is that the status of $(\lambda z.z-4~5)$ is ambiguous, parenthesis should put here to clarify the order of operations. Is it 45 or 4 apply to 5, or (z-4) applied to 5 ?, or $(\lambda z.(z-4))$ applied to $5$ ? – Denis May 30 '13 at 10:46
  • @dkuper there is a space between 4 and 5. – jason May 30 '13 at 10:48
  • The only way to get a number in the end is the parenthesis I put in the answer. otherwise your $z$ is left hanging. It corresponds in your expression to "-" having priority over ".", having itself priority over application. – Denis May 30 '13 at 10:52

1 Answers1

1

The parentheses are pretty bad, here is my guess on what the expression should be in order to evaluate to a number in the end:

$(\lambda x.\lambda y.(x + ( \lambda x.x+1) (x+y)))~( (\lambda z.(z-4))~5)~10$

Then you just have to reduce everything. Here is a step-by-step reduction:

$$\begin{array}{l} (\lambda x.\lambda y.(x + ( \lambda x.x+1) (x+y)))~( (\lambda z.(z-4))~5)~10\\ \to (\lambda x.\lambda y.(x + (x+y+1)))~(5-4)~10\\ \to (\lambda x.\lambda y.(2x+y+1))~1~10\\ \to (\lambda y.(2*1+y+1))~10\\ \to (2*1+10+1)\\ \to 13 \end{array}$$

Denis
  • 6,945
  • 1
  • 21
  • 22
  • I followed these steps : (λx.λy.(x+(λx.x+1)(x+y))) ((λz.(z−4)) 5) 10 = (λx.λy.(x+(λx.x+1)(x+y))) 1 10 =(λx.λy.(13)) = 13 is that true? – jason May 30 '13 at 10:57
  • the $13$ is good, but the intermediate steps are weird. In particular the last one is not correct. I put the correct steps in the answer. – Denis May 30 '13 at 10:59