In lambda calculus, how many fixed-point combinators are there? [closed]

In lambda calculus, how many fixed-point combinators are there?

I am familiar with Curry’s paradoxical combinator a.k.a. the $Y$-combinator and Turing’s fixed-point combinator, $\Theta$, which are both fixed-point combinators and I am aware there are others.

• Is there a tally of how many fixed-point combinators there are?
• Do we know if all have been found?
• Are there infinitely many? Do we know of a way to generate arbitrary many different fixed-point combinators?

Solution 1:

From your third point, I assume that you ask this question not up to $\beta$-equivalence? In that case, there are infinitely many, because of the identity combinator $1 = \lambda x. x$.

For example: define $v = \lambda xy. (1y)(xxy)$. Then $vv$ is a fixed point combinator. (Note the similarity with $\Theta$.)

I cannot say anything about the case where we identify $\beta$-equivalent terms, however.

Solution 2:

The nLab article on fixed-point combinators mentions this:

Another construction is due to (Klop 07): $$Y_K = LLLLLLLLLLLLLLLLLLLLLLLLLL$$ where $$L = \lambda abcdefghijklmnopqstuvwxyzr. r (thisisafixedpointcombinator)$$

Note that $Y_K$ is $L$ repeated 26 times, and the string $thisisafixedpointcombinator$ contains 27 characters.

This seems to suggest a way to generate fixed-point combinators. The linked paper (Klop07) also mentions this:

how to derive new fixed point combinators from given ones

@mohottnad brought to my attention the following excerpt from the Wikipedia article on Fixed-point combinator:

In untyped lambda calculus fixed-point combinators are not especially rare. In fact there are infinitely many of them. (Bimbó 11)

References

• Jan Willem Klop, New Fixed Point Combinators from Old, in
  Reflections on Type Theory, Lambda Calculus, and the Mind: Essays Dedicated to Henk Barendregt on the Occasion of his 60th Birthday
• Bimbó, Katalin (27 July 2011). Combinatory Logic: Pure, Applied and Typed. p. 48. ISBN 9781439800010.