Problem # 10

[Next] [Previous] [Up]

Problem # 10

Submitted by Richard Statman
Date: 1993
Statement. Do uniform universal generators exist?

A term $M$ is a uniform universal generator iff there is a non-trivial context $C[*]$ such that $M ↠ C[N ]$ for each closed term $N$ . 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 $C[ *]$ is required to have the form $P *$ , so $C[N ]$ is $P N$ , 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