Lambda calculus help

Question

Donc, je suis totalement coincé sur cette partie d'un problème. Ce serait génial si quelqu'un pouvait aider ...

Montrer que le terme ZZ où Z est λz.λx. x (z z x) satisfait l'exigence pour les combinateurs à virgule fixe que ZZM = β M (ZZM).

Answer 1

Ceci est complètement trivial. Vous appliquez simplement la définition de deux fois β-réduction:

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

où> est le β-réduction. Par conséquent, Z Z M β se réduit en M (Z Z M) en deux étapes, d'où Z Z M = β M (Z Z M).