# A smaller conservative base

## Brent Kerby — 2002-10-10 22:00:43

    This may seem insignificant at this point, but the following base has

    conservative completeness:

             [A] i ==  A

     [C] [B] [A] q ==  [A [C] B] [B]

    Remember, conservative completeness means that this is enough to form all

    combinators except those with a destructive effect, and is equivalent to the

    base {i, dip, cons, dup}. The simplest known conservative base before was

    {i, j'} where

     [E] [D] [C] [B] [A] j'   == [[D] A [E] B] [C] B

    Anyhow, here's how to construct the basic combinators from {i,q}:

      dip  == [] [[]] q i i q i i

      unit == [] [] q i

      swap == [] [] q [[]] q i i q i i      (== unit dip)

      dup  == [] [[]] q i i [] [i] q q i

      cat  == swap [i] swap q [] swap i

      cons == [unit] dip cat

    (the searcher is too slow to find minimal constructions of cat, dup, and

    cons in terms of q and i alone). Well, here's the proof that these work:

    For dip:

       [B] [A] [] [[]] q i i q i i

    == [B] [[] [A]] [] i i q i i

    == [B] [[] [A]] i q i i

    == [B] [] [A] q i i

    == [A [B]] [] i i

    == [A [B]] i

    == A [B]

    For unit:

       [A] [] [] q i

    == [[A]] [] i

    == [[A]]

    For swap, there's no real need since swap == unit dip ...

    For cat:

       [B] [A] swap [i] swap q [] swap i

    == [A] [B] [i] swap q [] swap i

    == [A] [i] [B] q [] swap i

    == [B [A] i] [i] [] swap i

    == [B A] [i] [] swap i

    == [B A] [] [i] i

    == [B A] [] i

    == [B A]

    For dup:

       [A] [] [[]] q i i [] [i] q q i

    == [[] [A]] [] i i [] [i] q q i

    == [[] [A]] i [] [i] q q i

    == [] [A] [] [i] q q i

    == [] [i [A]] [] q i

    == [[] i [A]] [i [A]] i

    == [[] i [A]] i [A]

    == [] i [A] [A]

    == [A] [A]

    You may have noticed the common "[] [[]] q i i", which has the effect of

    burying a "[]" under one item. Actually "[] [[A]] q i i" in general buries

    an "[A]" (i.e., does "[A] swap").

    So it works. There you have it! The question arises, is there a

    two-combinator conservative base in which both combinators take no more than

    2 parameters (as opposed to the 3 of q). I'm doubting it; if there was, it

    would have to satisfy these conditions

    1) one combinator would have to contain no quotations (like "i" or "k"),

    otherwise there could be no way to eliminate a solitary "[]" (because every

    combinator would leave a quotation hanging) and thus no way to construct

    "i".

    2) the other combinator would have to contain a quotation with two variables

    inside (like "cons" or "cat") and also would have to have a nested quotation

    (like "unit" or "cons". Also this combinator cannot use a variable twice,

    otherwise there would be no way to take a "cons" of two unknowns, because

    there would be an unknown hanging, and we cannot destroy an unknown in a

    conservative system (we can destroy a nil, "[]", and such, but that's a

    different story).

    This tells us that in essence the second combinator is "cons" or else is

    very similar to "cons", and that the first combinator has to have to have

    duplications (since one of them must, and the second one cannot) but no

    quotations. We might suspect a base like such

      [B] [A] ?    ==  A A B

      [B] [A] cons ==  [[B] A]

    But from this it seems impossible to construct "dip" ...

    - Brent