Lambda calculus help

0
votes

So i'm totally stuck on this one part of a problem. It would be awesome if someone could help.........

Show that the term ZZ where Z is λz.λx. x(z z x) satisfies the requirement for fixed point combinators that ZZM =β M(ZZM).

1
lambda-calculus
Try math.stackexchange.com. This question isn't exactly relevant to programming directly. – Noldorin
sorry. This was homework from a comp sci class, thought it would fit here. – user516849
@Noldorin: Why not? The lambda calculus is a programming language, why wouldn't questions about it be on topic here? I would expect the average mathematician to know significantly less about the lambda calculus than the average computer scientist. – sepp2k
@sepp2k: You're rather misinformed I'm afraid. Lambda calculus is really just mathematics, and was invented by a mathematician/logician. It's not a programming language in the modern sense (in its pure form). – Noldorin

1 Answers

1
votes

This is completely trivial. You just apply the definition of β-reduction two times: 

 Z Z M = (λz.λx. x(z z x)) Z M > (λx. x(Z Z x)) M > M (Z Z M)

where > is the β-reduction.

Therefore Z Z M β-reduces to M (Z Z M) in two steps, hence Z Z M =β M (Z Z M).