1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – chi
    Commented Apr 20, 2018 at 10:22
  • $\begingroup$ The first two are allowed, the third one is not. $\endgroup$ Commented Apr 20, 2018 at 15:32

2 Answers 2

1
$\begingroup$

$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.

$\endgroup$
0
$\begingroup$

Set $x_1 = x$ and $x_{n+1} = B x_n$, where $x ∈ \{B, C, K, W\}$; and note that - up to η-equivalence, $x_n = x_{n+1} I$, since $B f I = f = B I f$ under η-equivalence. We can then also write $x_0 = x I$. The combinators $\{B, C, K, W\}$ are given by the rules $$I x = x,\quad B x y z = x (y z),\quad C x y z = x z y,\quad W x y = x y y,\quad K x y = x.$$

Up to η-equivalence $B_0 = B I = I$.

Instead of explaining the general case, it should suffice to see an example: $$\begin{align} x v (z y) (y x) &= I x v (z y) (y x)\\ &= B_4 I x v (z y) y x\\ &= B_3 (B_4 I) x v z y y x\\ &= C_3 X_b x v y z y x\\ &= C_4 (C_3 X_b) x v y y z x\\ &= C_5 (C_4 (C_3 X_b)) x v y y x z\\ &= C_4 (C_5 (C_4 (C_3 X_b))) x v y x y z\\ &= C_3 (C_4 (C_5 (C_4 (C_3 X_b)))) x v x y y z\\ &= C_1 (C_3 (C_4 (C_5 (C_4 (C_3 X_b))))) v x x y y z\\ &= W_4 X_c v x x y z\\ &= W_2 (W_4 X_c) v x y z\\ &= K_2 X_w v w x y z\\ &= X_k v w x y z, \end{align}$$ where $$ X_b = B_3 (B_4 I) = B_3 B_3,\quad X_c = C_1 (C_3 (C_4 (C_5 (C_4 (C_3 X_b))))),\\ X_w = W_2 (W_4 X_c),\quad X_k = K_2 X_w. $$ The $X_b$ sub-term applies to your question. The remainder applies to the more general question that you didn't ask.

You could also write it as $$K_2 (W_2 (C_1 (W_4 (C_3 (B_3 (C_4 (B_4 C_2))))))) v w x y z = x v (z y) (y x).$$

Edit: Before I forget, your example: $$\begin{align} a(bcd)(ef) &= Ia(bcd)(ef)\\ &= B_3Ia(bcd)ef\\ &= B_2(B_3I)a(bc)def\\ &= B_2(B_2(B_3I))abcdef\\ &= B_2(B_2B_2)abcdef \end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.