It is known that the combinators $S,K$ form a basis for lambda calculus. It's also known that the iota combinator $\lambda x.((x S) K)$ is a basis.

Chris Barker found that the iota combinator allows a 2-symbol basis by encoding the alternating associativity. This is described by the word translation function $\tau:\{0,1\}^*\to\mathrm{COMB}$, where $\mathrm{COMB}$ is an expression of combinators with normal application notation: $$ \begin{align*} \tau(\varepsilon)&= I\\ \tau(x0)&=((\tau(x)S)K)\\ \tau(x1)&=(S(K\tau(x))) \end{align*} $$ I now wondered what happens if you add the restriction of "alternating associativity" for a 1-symbol basis, specifically: $\tau_{l,r}:\{1\}^*\to\mathrm{COMB}$: $$ \begin{align*} \tau_{l\mid r}(\varepsilon)&= E\\ \tau_l(x1)&=(L\tau_r(x))\\ \tau_r(x1)&=(\tau_l(x)R) \end{align*} $$ The translation would start with $\tau_l$ if the length of the word is even and $\tau_r$ if the length is odd; such that $E$ will only appear on the left side of the innermost application.

With $E,L,R$ being arbitrary (preferably common) combinators, does such a basis exist?



You must log in to answer this question.

Browse other questions tagged .