[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |
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].)
[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |