[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].)


Richard Statman. There is no hyperrecurrent S,K combinator. Research Report 91–133, Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA, 1991.
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]