Unverified

The Number of Fixed Points of a Combinator

For a closed lambda term $F$ , let

\operatorname{Fix}(F)=\{[X]_{\beta}: FX =_\beta X\}

be the set of beta-equivalence classes of its fixed points. Which cardinalities can $\operatorname{Fix}(F)$ have as $F$ ranges over all closed lambda terms?

Download

Abstract

Classify the possible numbers of fixed points of a closed term in lambda-beta calculus. If one fixed point is in normal form, the source records a dichotomy between exactly one and infinitely many.

Background and progress

Benedetto Intrigila submitted this problem in 2000. The source records the theorem that a combinator having a fixed point in normal form has either exactly one fixed point or infinitely many, and leaves the unrestricted classification open. The status statements here follow the TLCA page's July 21, 2014 snapshot and have not been independently updated after that date [Intrigila, 2000]. The original open problem appears at https://tlca.di.unito.it/opltlca/opltlcasu32.html.

Reference papers

The Number of Fixed Points of a CombinatorBenedetto IntrigilaTLCA Open Problem List · 2000 ↗

The Number of Fixed Points of a Combinator

Coming soon

Organizer