Binary Lambda Calculus, Binary Mode, 3 characters (ascii-encoded)

HR.

Interpreted as incomplete segments of Binary Lambda Calculus, writing \ for lambda, * for application and De Bruijn indices for variables:

H = 01001000 = * \ 1 \
R = 01010010 = * * \ 1
. = 00101110 = \ 1 3

Suppose x and y are valid terms.

Then,

  H x
= * \ 1 \ x
= \ x

  R x y
= * * \ 1 x y
= * x y

  R .
= * .
= * \ 1 3
= 3

Thus we can use H as \, R as *, and R. as 3.

For 2 and 1, suppose we have any valid term z.

Then,

  R H 3 z
= * / 3 z
= 2

  R H R H\ 3 z z
= R H 2 z
=  
* /\ 2 z
  = 1

(Note that freeFree variables get decremented in beta-reduction when usingwith De Bruijn indices)

As for the choice of z, we can use z = HHHR. = \ \ \ 3 (or if we allow free variables in our program, we can just use R.3).

Finally, to show we don't need more than 3 variables, we can implement SKI combinator calculus:

I = \ 1
K = \ \ 2
S = \ \ \ * * 3 1 * 2 1

Written using our 3 characters, these are

I = HRHRHR.HHHR.HHHR.
K = HHRHR.HHHR.
S = HHHRRR.RHRHR.HHHR.HHHR.RRHR.HHHR.RHRHR.HHHR.HHHR.

Which can be applied to each other in arbitrary ways using R.