Submitted by Richard Statman
Statement. A ﬁxed point combinator from and alone?
Problem Origin. The problem was ﬁrst posed by Raymond Smullyan.
The combinator satisﬁes the reduction rule and the combinator is as usual . Is there an applicative combination of and which is a ﬁxed point combinator? The problem was originally proposed in [Smullyan, 1985].
Comments by Richard Statman: Note that is always a ﬁxed point of but it appears that cannot be abstracted to give a ﬁxed point combinator such that . If it is required that as with Turing’s ﬁxed point combinator then it can be shown [Statman, 1993, McCune and Wos, 1991] that no , combination works.