Re: single-combinator basis with direct algebraic characterisation?

From: r.e.s. (r.s_at_ZZmindspring.com)
Date: 11/03/04 

Date: Wed, 03 Nov 2004 18:53:00 GMT

"William Elliot" wrote ...
> [r.e.s. wrote ...]
> "William Elliot" wrote ...
>> r.e.s. wrote:
>>
>>> Combinators K,S can be characterised as satisfying
>>> K a b = a
>>> S a b c = a c (b c)
>>> for arbitrary terms a,b,c.
-snip-
>> For more information, here's an article I found on the web ...
>> http://www.cs.uu.nl/people/jeroen/article/combinat/
>
> Didn't download propertly.
> Did he give \f.fKSK or something else for the
> one-combinator base?

He -- the author is Jeroen Fokker at Utrecht University --
lists four that were already in the literature, including
\f.fKSK, and derives several others, including \f.fS(\xyz.x).

In all of these, S is as I've characterised it (i.e.,
\abc.ac(bc)).

>> > Are you sure S isn't \abc.ac(cb) ?
>> > As I recall, isn't my S and K a base?
>
>> I don't know about yours, but the S and K that I
>> describe above form a standard two-combinator basis.
>
> Can you show tau = \xy.yx combination of your S and K?

It's easy to confirm (S(K(S(SKK)))K) works; or, see the
derivation at http://www.wordiq.com/definition/Combinator

> S(SK)ab = SKb(ba) = K(ba)(bab) = ba with my S and K.

Yes, but that's far from establishing your "S",K as a basis.
Denote your \abc.ac(cb) by $, and retain S for \abc.ac(bc).
Following the procedure outlined at the cited page, $ can
be expressed in terms of S,K alone. Can you show, on the
other hand, that S can be expressed in terms of $,K alone?

--r.e.s.

Relevant Pages

  • Re: single-combinator basis with direct algebraic characterisation?
    ... "William Elliot" wrote ... ... Yes, but that's far from establishing your "S",K as a basis. ... Denote your \abc.acby $, ... other hand, that S can be expressed in terms of $,K alone? ...
    (sci.logic)
  • Re: Day of the Jackal - last night ITV4
    ... panel let alone a whole car powered by a sprayer off the battery. ... there is the ending - when I first saw this film as a youngster I ... acting and writing and with some basis in fact. ...
    (uk.media.tv.misc)
  • Re: On gendered pronouns, with some griping
    ... are better left alone (in the hope that they will quietly wither ... on the basis that you don't know his sex, or as "she" on the basis ... that she's more likely to be female? ...
    (alt.usage.english)
  • Re: On gendered pronouns, with some griping
    ... are better left alone (in the hope that they will quietly wither ... on the basis that you don't know his sex, or as "she" on the basis ... that she's more likely to be female? ...
    (alt.usage.english)
  • Re: Keith Richards on the blues & recording
    ... rock and roll music product, and stand on that basis ... alone. ... Nobody will ever do that again. ...
    (alt.guitar.amps)