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

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

Problem #53

Originator: Richard Statman
Date: June 1993

Summary: Are there hyper-recurrent combinators?

A term M in Combinatory Logic or λ-calculus is recurrent if N →^* M whenever N ↔^* M (this notion is due to M. Venturini-Zilli.) Let’s call M hyper-recurrent if N is recurrent for all N ↔^* M. (Equivalently, M is hyper-recurrent if P →^* Q →^* P whenever P ↔^* Q ↔^* M.) Are there any hyper-recurrent combinators? (The problem comes up immediately when the Ershov-Visser theory [Vis80] for ↔^* is applied to →^*. It is known that hyper-recurrent combinators don’t exist for Combinatory Logic [Sta91].)

References

[Sta91]

Richard Statman. There is no hyperrecurrent S,K combinator. Research Report 91–133, Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA, 1991.

[Vis80]

A. Visser. Numerations, lambda calculus, and arithmetic. In Hindley and Seldin, editors, Essays on Combinatory Logic, Lambda-Calculus, and Formalism, pages 259–284. Academic Press, 1980.

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

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