1
$\begingroup$

Help would be appreciated. The notes are poor on the subject, and I am clueless.

Verify the following equalities:

  • Verify the equality $\mathsf{SIII}=_β\mathsf{I}$ where $\mathsf{S} = λxyz.(xz)(yz) \quad \mathsf{I}= λx.x$

  • Verify the equality $\operatorname{twice} (\operatorname{twice}) f x =_β f(f(f(f x)))$ where $\operatorname{twice} = λfx.f(f x)$

2 Answers 2

2

Try substituting the arguments in the definitions of the combinators.

  • 0
    Note that application associates to the left, so twice twice$f$x really means (((twice twice) f) x)2012-01-22
0

I am posting this answer to make solutions more clear. $ \mathsf{SIII}=_\beta (λxyz.(xz)(yz)) \mathsf{III} =_\beta (\mathsf{II})(\mathsf{II}) $ Remember that $\mathsf{I}=\lambda x.x$ is the operator that does nothing. This means that for every lambda expression $M$, you have $\mathsf{I}M =_\beta M$.

This implies that: $\mathsf{II} =_\beta (\lambda x.x)(\lambda x.x)=\lambda x.x = \mathsf{I}$ And so we have $ (\mathsf{II})(\mathsf{II}) =_\beta (\mathsf{I})(\mathsf{I}) =_\beta = \mathsf{II} =_\beta \mathsf{I}$

The second one is easier

$ \operatorname{twice} \operatorname{twice} f x = \operatorname{twice} (\operatorname{twice} f) x = \operatorname{twice} f (\operatorname{twice} f x) = \operatorname{twice} f f(f(x) = f(f(f(f(x)))) $