[Next] [Previous] [Up]

#### Problem # 4

Submitted by Richard Statman

Date: 1985

Statement. A ﬁxed point combinator from and alone?

Problem Origin. The problem was ﬁrst posed by Raymond Smullyan.

[PRINT this PROBLEM]

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.

##### References for # 4

[McCune and Wos, 1991] McCune, W. and Wos, L. (1991). The absence
and the presence of ﬁxed point combinators. Theoretical Computer Science,
87:221–228.

[Smullyan, 1985] Smullyan, R. (1985). To Mock a Mockingbird. Knopf.

[Statman, 1993] Statman, R. (1993). Some examples of non-existent
combinators. Theoretical Computer Science, 121:441–448.

[Next] [Previous] [Up]

Last modified: July 21, 2014