[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #52 (Solved !)

Originator: Richard Statman
Date: June 1993

Summary: Is there a fixed point combinator Y for which Y ↔^* Y(SI)?

It has been remarked by C. Böhm [Bar84] that Y is a fixed point combinator if and only if Y ↔^* (SI)Y (Y and SIY are convertible). Also, if Y is a fixed point combinator, then so is Y(SI). Is there is a fixed point combinator Y for which Y ↔^* Y(SI)?

Remark

This was solved by Benedetto Intrigila [Int97] who showed that there is no such fixed point combinator.

References

[Bar84]

Henk Barendregt. The Lambda Calculus, its Syntax and Semantics. North-Holland, Amsterdam, second edition, 1984.

[Int97]

Benedetto Intrigila. Non-existent statman’s double fixed point combinator does not exist, indeed. Information and Computation, 137(1):35–40, 1997.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]