Page 186

Location: Chapter 19, final Exercise

Exercise (after the Appendix)

In terms of \(B\), \(C\), \(S\), and \(I\), find a combinator \(A\) satisfying the condition \(Axyz=xz(zy)\). The problem should be divided into three parts: ...

Solution

\[ A = C(BBS)(CI) \]

Short explanation

As suggested by the text, and according to the algorithm given in the Appendix, the solution proceeds in three steps:

First, a distinguished \(z\)-eliminate \(A_1\) of the expression \(X=xz(zy)\) must be found. By Rule 3a, this in turn requires to find:

  • a distinguished \(z\)-eliminate of \(xz\), which is \(x\) (Rule 2);
  • a distinguished \(z\)-eliminate of \(zy\), which by Rule 3c is \(CIy\).

Hence it is \(A_1=Sx(CIy)\).

The second step consists of finding a distinguished \(y\)-eliminate \(A_2\) of \(A_1\): by Rule 3b (and Rule 2), one has immediately

\[ A_2 = B(Sx)(CI)\;. \]

Finally, one needs a distinguished \(x\)-eliminate \(A\) of \(A_2\): again according to Rule 3c, to find it one must have a distinguished \(x\)-eliminate of \(B(Sx)\). This latter term is \(BBS\) (applying Rule 3b).

Application of Rule 3c then yields:

\[ A = C(BBS)(CI)\;, \]

as can be verified by feeding the equation \(Axyz=xz(zy)\) to the combinator-finder program (with the BCSI command-line option) as well as by explicit computation:

\[ \begin{align} Axyz =~& C(BBS)(CI)xyz=BBSx(CI)yz=B(Sx)(CI)yz=\\ =~& Sx(CIy)z=xz(CIyz)=xz(Izy)=xz(zy)\;. \end{align} \]