Wikipedia: Y combinator

Difference (from prior author revision) (major diff, minor diff)

Changed: 1,15c1

The Y combinator or Y constructor is a formula in lambda calculus which allows the definition of recursive functions in that formalism.

Church invented the Y combinator:

Y = (\h . (\x. h (x x)) (\x. h (x x)))

which has the cute property that it reproduces whatever argument we give it:

Y A ===> A (Y A)
===> A (A (Y A))
===> A (A (A (Y A)))
===> A (A (A (A (Y A))))
===> ...

The Y combinator or Y constructor is a formula in lambda calculus which allows the definition of recursive functions in that formalism. See the article about lambda calculus for a detailed explanation.