\documentclass{rtaloop}
\rtalabel{CL}


\begin{document}
\begin{problem}{Richard Statman}{}{June 1993}

\begin{abstract}
Are there \emph{hyper-recurrent} combinators?
\end{abstract}

A term $M$ in Combinatory Logic or $\lambda$-calculus is {\em recurrent\/}
if $N \rightarrow^* M$ whenever 
$N \leftrightarrow^* M$ (this notion is due to M. Venturini-Zilli.)
Let's call $M$ {\em hyper-recurrent\/} if $N$ is recurrent 
for all $N \leftrightarrow^* M$. (Equivalently, $M$ is hyper-recurrent
if $P \rightarrow^* Q \rightarrow^* P$ whenever 
$P \leftrightarrow^* Q \leftrightarrow^* M$.)
Are there any 
hyper-recurrent combinators? 
(The problem comes up immediately
when the Ershov-Visser theory \cite{V80:cl} for $\leftrightarrow^*$ is applied to
$\rightarrow^*$. 
It is known that hyper-recurrent combinators don't exist for Combinatory
Logic \cite{S91:cmu}.)

\end{problem}
\end{document}
