Skip to content
scrambled
Programming Language Theory Flashcard

What

Books Concepts Deckpure-lambda-calculus

Question

What's the relation between the y-combinator and the omega combinator?

Answer

The small omega combinator:

ω=λx. x x

The big omega combinator:

Ω=(λx. x x) (λx. x x)

The Y-combinator:

Y=λf. (λx. f x x) (λx. f x x)

Some similarities in structure:

  • Each term in the Y-combinator's body is a slightly modified version of the small omega combinator - λx. f x x vs λx. x x.

  • Self-application pattern.