Curry y combinator

$$\text{fix} = \lambda f.\ (\lambda x.\ f\ (x\ x))\ (\lambda x.\ f (x\ x))$$

• Details

  $$\begin{aligned} \text{fix}\ g &\to [f \mapsto g] (\lambda x.\ f\ (x\ x))\ (\lambda x.\ f\ (x\ x)) \\ &\to (\lambda x.\ g\ (x\ x)) \ (\lambda x.\ g\ (x\ x)) \\ &\to [x \to \lambda x.\ g\ (x\ x)] g\ (x\ x) \\ &\to g\ ((\lambda x.\ g\ (x\ x))\ (\lambda x.\ g\ (x\ x))) \\ &= g\ (\text{fix}\ g) \end{aligned}$$

  • In a Call by value evaluation strategy, this diverges because it continues to evaluate $\text{fix}\ g$.
  • In a Call by name evaluation strategy, $\text{fix}\ g$ does not diverge because $g$ gets applied to $\text{fix}\ g$.