1

I have the following and am asked to evaluate it (I've posted this question elsewhere but I have a new worry with evaluating the function).

$[[\lambda f.\lambda m. f(m + m^2))]([\lambda n.2n])](3)$

I'm worried about mis-evaluating this because I'm putting brackets in the wrong place.

Here's my reasoning thus far.

  1. I bind $\lambda n.2n$ to $f$ to get the following:

$[[\lambda m.[\lambda n.2n](m+m^2)](3).$

  1. Then I bind $(m+m^2)$ to $n$ to get the following:

$[\lambda m.2(m+m^2)](3)$

  1. And then finally I bound (3) to $m$ to get this:
    $2(3+3^2)$ which equals 36.

I'm worried that at (2) I should bind THREE to $m$ and gotten this instead:
$\lambda n.2n(3+3^2)$ and THIS should be my end result.

Does anyone have any thoughts, tips, suggestions or see any mistakes or anything? Help would be greatly appreciated; I'm really struggling with Lambda Calculus stuff.

Rusty
  • 245

1 Answers1

1

Sorry for such a late response. I hope it at last helps others if you already figured everything out.

There is a Church-Rosser theorem which deals with your concern exactly. It states that the order of reductions is irrelevant and if we apply, say, $2$ different reductions to the expression yielding $2$ different resulting expressions, then there must be an expression that is reachable from both of them. In your example, $24$ will be reachable no matter what we decide on step $2$.

Let us now discuss your steps. Almost all of your reductions are done correctly (except the one you worry about), and I am quite sure that $2(3+3^2)$ is $24$ and not $36$ :).

You say that you worry about substituting $3$ for $m$ in the expression $[\lambda m.[\lambda n.2n](m+m^2)]$, but you then make a mistake in doing so (you forget brackets around $\lambda n.2n$). The result should be \begin{equation} [\lambda n.2n](3+3^2) \end{equation} which is then also $24$.

Leaving out those brackets changed the semantics of your expression because by definition $\lambda$ goes as far as possible, so by removing those brackets you were left with just the $\lambda$-abstraction $\lambda n. 2n(3+3^2)$ but it was supposed (all along through task) to be the application of $\lambda n. 2n$ onto $(3+3^2)$.

Sandro Lovnički
  • 225