[Next] [Previous] [Up]

#### Problem # 10

Submitted by Richard Statman

Date: 1993

Statement. Do uniform universal generators exist?

[PRINT this PROBLEM]

A term is a uniform universal generator iff there is a non-trivial
context such that for each closed term . The above
question was ﬁrst stated in [Statman, 1993], and it is open for either CL (with
weak reduction) or lambda-calculus (with - or -reduction). If the context
is required to have the form , so is , then it can be
shown [Statman, 1993] that uniform universal generators do not exist for
combinatory logic.

##### References for # 10

[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