# Is there a combinator that introduces brackets to a combinatory logic expression using just B?

Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this:

$Xabcdef=a(bcd)(ef)$.

Is it possible to express $X$ using just the $B$ combinator, defined by

$Babc=a(bc)$?

Is this possible in general? That is, if I have a string of letters without brackets, is there always a combinator in terms of $B$ only that parenthesizes my expression in the way I want, leaving the order of the letters unchanged?

• What is a "combinator in terms of a $B$ only", precisely? I.e. are $BBBabcdef, B(BB)abcdef, Ba(Bbcd)(Bef)$ allowed as "only in terms of $B$"? (Note that none of these is a solution, I just want to understand the rules of the game.) Which ones could be allowed?
– chi
Apr 20 '18 at 10:22
• The first two are allowed, the third one is not. Apr 20 '18 at 15:32

$X=B(BBB)(BB)$ answers the first question. Indeed,
$B(BBB)(BB)abcdef=BBB(BBa)bcdef=B(B(BBa))bcdef=B(BBa)(bc)def=BBa(bcd)ef=B(a(bcd))ef=a(bcd)(ef).$
For the second question, yes, this may be done in general. Here's a rough proof: if we have $Xabc\ldots xyz = (\textrm{expr})(yz)$, this becomes $Xabc\ldots xyz=B(\textrm{expr})yz$, so $Xabc\ldots x = B(\textrm{expr})$. If $(yz)$ is nested inside other brackets, like, for example, $Xabc\ldots xyz=(\textrm{expr})(x(yz))$, we get $Xabc\ldots xyz=B(\textrm{expr})x(yz)=B(B(\textrm{expr})x)yz$, and again we may then consider just $Xabc\ldots x=B(B(\textrm{expr})x)$. We may then do a further step: $Xabc\ldots x=B(B(\textrm{expr})wx)=BB(B(\textrm{expr}))x$, which means that $Xabc\ldots w=BB(B(\textrm{expr}))$. Continuing doing this, we end up with just $X$ on the left hand side and an expression involving (possibly bracketed) $B$'s on the right hand side.