On 23/07/2015 08:02 AM, Mr wrote:
> Orchid Win7 v1<voi### [at] devnull>  wrote:
>> On 22/07/2015 08:32 AM, scott wrote:
>>> An interesting read... What are the uses of SKI then, apart from just
>>> making simple algorithms take up a million characters to encode?
>>
>> Erm... that's pretty much the only use.
>
> ROTFL !!! isn't that being slightly pervert ?! :)
>
> I'm sure however that it could find unpredicted real applications one day!

Well, no, the SKI combinators are of theoretical interest, because they 
show you something about how small a Turing-complete programming 
language can be.

It's like, Turning machines have to *practical* use (unless you enjoy 
writing excruciatingly complicated programs!), but they are 
theoretically important.

Of course, the Iota calculus is even smaller, consisting of only *one* 
predefined function. If we write it as X (rather than Iota), then its 
definition is

   X = λ a → a S K

Therefore we have

   XX = XSK = (XS)K = SSKK = SK(KK)

If we eta-expand that, we find

   λ x → SK(KK)x = λ x → Kx(KKx) = λ x → x

which is the definition of I. Therefore

   XX = I

Similarly,

   X(XX) = XI = ISK = SK
   X(X(XX)) = X(SK) = SKSK = KK(SK) = K
   X(X(X(XX))) = XK = KSK = S

So, using only X, we can recover S, K and I, which we already know to be 
Turing-complete. Therefore, any possible computable function can be 
constructed just using X and brackets.

OTOH, if you look at the size of "S" verses "X(X(X(XX)))", you can see 
that anything in the Iota calculus is going to be *really huge*!

This seems to be the general thing; the simpler your programming 
language, the more complicated your programs get!

Post a reply to this message