\documentclass{rtaloop}
\rtalabel{Scomb-word}


\begin{document}
\begin{problem}{Henk Barendregt}{\cite{barendregt:lambda75:open}}{1975}

\begin{abstract}
Is the word problem for the $S$-combinator decidable?
\end{abstract}

The word problem for the $S$-combinator is: Given two ground terms
build only of the constant $S$ in combinatory logic (that is with an
application operator written as juxtaposition, and parantheses), are
they convertible in the system consisting only of the definition of
the $S$-combinator
\[
S x y z \rightarrow (x z) (y z)
\]
Is the word-problem for the $S$-combinator decidable? 
See also \cite{Waldmann:rta98} and \cite{Waldmann:phd} for more background.

A related problem is the word problem for proper combinators of order
smaller than 3 ($S$ is of order 3), see
\rtaref{smallorder-combinators-word}.  


\end{problem}
\end{document}