← All problems
Unverified

Are there hyper-recurrent combinators?

The source page states the original problem together with its recorded qualifications and progress updates as follows.

A term MM in Combinatory Logic or λ\lambda-calculus is recurrent if N→∗MN \rightarrow^* M whenever N↔∗MN \leftrightarrow^* M (this notion is due to M. Venturini-Zilli.) Let's call MM hyper-recurrent if NN is recurrent for all N↔∗MN \leftrightarrow^* M. (Equivalently, MM is hyper-recurrent if P→∗Q→∗PP \rightarrow^* Q \rightarrow^* P whenever P↔∗Q↔∗MP \leftrightarrow^* Q \leftrightarrow^* M.) Are there any hyper-recurrent combinators? (The problem comes up immediately when the Ershov-Visser theory [Statman, 1993] for ↔∗\leftrightarrow^* is applied to →∗\rightarrow^*. It is known that hyper-recurrent combinators don't exist for Combinatory Logic [Statman, 1993].)

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu