Skip to main content
deleted 409 characters in body
Source Link

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

Indeed, we can say more. If we define the combinator $D$ with the rule $Dabcd=ab(cd)$, then this expression of bracketed $B$'s may be replaced by an unbracketed expression involving $B$'s and $D$'s. For example, in the first question, $X=B(BBB)(BB)$ is the same as $X=B(DB)D=BBDBD=DDBD$, since $D=BB$. (In fact, $BBabcd=B(ab)cd=ab(cd)$.) Indeed, $DDBDabcdef=DB(Da)bcdef=B(Da)(bc)def=Da(bcd)ef=a(bcd)(ef)$.

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

Indeed, we can say more. If we define the combinator $D$ with the rule $Dabcd=ab(cd)$, then this expression of bracketed $B$'s may be replaced by an unbracketed expression involving $B$'s and $D$'s. For example, in the first question, $X=B(BBB)(BB)$ is the same as $X=B(DB)D=BBDBD=DDBD$, since $D=BB$. (In fact, $BBabcd=B(ab)cd=ab(cd)$.) Indeed, $DDBDabcdef=DB(Da)bcdef=B(Da)(bc)def=Da(bcd)ef=a(bcd)(ef)$.

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

Source Link

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

Indeed, we can say more. If we define the combinator $D$ with the rule $Dabcd=ab(cd)$, then this expression of bracketed $B$'s may be replaced by an unbracketed expression involving $B$'s and $D$'s. For example, in the first question, $X=B(BBB)(BB)$ is the same as $X=B(DB)D=BBDBD=DDBD$, since $D=BB$. (In fact, $BBabcd=B(ab)cd=ab(cd)$.) Indeed, $DDBDabcdef=DB(Da)bcdef=B(Da)(bc)def=Da(bcd)ef=a(bcd)(ef)$.