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