Dance of the Starlings

In this birdwatching paper our binoculars are focused upon a particular bird from Smullyan’s enchanted forest of combinatory birds (Smullyan in To Mock a Mockingbird, and other logic puzzles. Alfred A. Knopf, New York, 1985), to wit the Starling. In the feathers of $\lambda$-calculus this bird has the plumage $\lambda$abc. ac(bc). This term is usually named S, reminiscent of its inventor Schönfinkel and also the combinatory ornithologist Smullyan. The combinator S is important for a variety of reasons. First, it is part of the {S,K}-basis for Combinatory Logic (CL). Second, there are several interesting questions and observations around S, mostly referring to termination and word problems. Our paper collects known facts, but poses in addition several new questions. For some of these we provide solutions, but several tough open questions remain.