[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #54

Originator: Richard Statman
Date: June 1993

Summary: In combinatory logic, is there a uniform universal generator?

Recall that M is a universal generator if each combinator P has a superterm Q such that M →^* Q. Call M a uniform universal generator if there exists a context C[·] such that, for each combinator P, we have M →^* C[P]. Is there a uniform universal generator? (For Combinatory Logic, if we restrict the context C[·] to be of the form (N ·), no such term exists [Sta92].)

References

[Sta92]

Richard Statman. A short note on a problem of Ray Smullyan. Technical report, INRIA-Rocquencourt, 1992.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]