[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 first 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]  
© 2006 Dip. Informatica - Universita di Torino
Last modified: July 21, 2014