![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyOK -- you all know about Iota, right? No? OK, recall:
Let ι=λx.xSK (where S and K are the usual S and K combinators, i.e., K=λx.λy.x and S=λx.λy.λz.xz(yz), and of course as usual I will denote the identity function λx.x.) Actually, instead of ι, let's call it U, since I'm going to be writing it a bunch.
Then U is what you might call a universal combinator: It generates both S and K, and thus all the functions of lambda calculus. Note that U itself is actually just the standard lambda-calculus encoding of the ordered pair (S,K); the nonobvious thing is that it generates the functions allowing for extraction. As follows:
U -- well, we've got U.
UU -- only thing to do is apply it to itself. If you go through and compute this (UU=USK=SSKK=SK(KK)=KI(SK)=I) you get I. (That is, λx.x.)
U(UU) -- obviously applying I to anything is stupid, so we compute UI. This is ISK, i.e. SK, i.e. KI.
U(U(UU)) -- Again, obviously applying KI to anything is stupid. But if we apply U to KI -- well, KI is "false"; doing this extracts the second element of the ordered pair; we now have K.
U(U(U(UU)) -- And K is "true"; taking UK extracts the second element of the ordered pair, gaining us S. And we're done, with K in 4 steps and S in 5.
But now let's say we take V, where we reverse the order of the pair: V=\x.xKS. Is V also universal? Can we still extract the K and the S?
The answer is yes, and while it's not really hard, it's certainly not as easy, which is why I'm bothering to write this down here. (Heidi showed me a solution once -- that was actually how I first learned it was possible, I had posed it to her as a problem, not knowing the answer -- but I don't remember what it might have been, and, you know, hard drive crashes... in any case, I'm pretty sure this solution is minimal.)
V -- OK, we've got V.
VV -- only possible next step. Compute this (VV=VKS=KKSS=KS) and you get KS.
VVV -- great, now we've got S. Though not by extracting it from the ordered pair.
That much is obvious; the problem is where to go from there. Taking V(VVV) gets you I (VS=SKS=KIS=I), but what we need is K. No, what you actually want to do is:
K=V(VVVVV)
Why's that? Well, how are we going to extract that K from λx.xKS? By duplicating it! SII=λx.xx, so one could do this by taking V(SII) to get KKS=K. But that uses up a lot of V's. Thing is, we can replace those I's with V's. Because, you see, VK=K (extracting the first element), thus SVV (or VVVVV) will work just as well as SII. And thus K=V(VVVVV). Yielding S in 3 and K in 6.
I'm pretty sure this is minimal, by which I mean with the help of an online "lambda calculator" (online since computer was down, you know) I checked all the 4-V and 5-V possibilities (or at least, I think I was exhaustive) and none of them worked.
Now I'm wondering how common such "universal combinators" are (guess: probably pretty common, however you measure it) and what the shortest one (measured however) might be. Not going to think about these things, though, this is really not stuff I know...
Addendum: Let's count length by "number of occurrences of variables, including right after a lambda", so e.g. I, K, and S have lengths 2, 3, and 7, while U and V both have length 12.
-Harry
Let ι=λx.xSK (where S and K are the usual S and K combinators, i.e., K=λx.λy.x and S=λx.λy.λz.xz(yz), and of course as usual I will denote the identity function λx.x.) Actually, instead of ι, let's call it U, since I'm going to be writing it a bunch.
Then U is what you might call a universal combinator: It generates both S and K, and thus all the functions of lambda calculus. Note that U itself is actually just the standard lambda-calculus encoding of the ordered pair (S,K); the nonobvious thing is that it generates the functions allowing for extraction. As follows:
U -- well, we've got U.
UU -- only thing to do is apply it to itself. If you go through and compute this (UU=USK=SSKK=SK(KK)=KI(SK)=I) you get I. (That is, λx.x.)
U(UU) -- obviously applying I to anything is stupid, so we compute UI. This is ISK, i.e. SK, i.e. KI.
U(U(UU)) -- Again, obviously applying KI to anything is stupid. But if we apply U to KI -- well, KI is "false"; doing this extracts the second element of the ordered pair; we now have K.
U(U(U(UU)) -- And K is "true"; taking UK extracts the second element of the ordered pair, gaining us S. And we're done, with K in 4 steps and S in 5.
But now let's say we take V, where we reverse the order of the pair: V=\x.xKS. Is V also universal? Can we still extract the K and the S?
The answer is yes, and while it's not really hard, it's certainly not as easy, which is why I'm bothering to write this down here. (Heidi showed me a solution once -- that was actually how I first learned it was possible, I had posed it to her as a problem, not knowing the answer -- but I don't remember what it might have been, and, you know, hard drive crashes... in any case, I'm pretty sure this solution is minimal.)
V -- OK, we've got V.
VV -- only possible next step. Compute this (VV=VKS=KKSS=KS) and you get KS.
VVV -- great, now we've got S. Though not by extracting it from the ordered pair.
That much is obvious; the problem is where to go from there. Taking V(VVV) gets you I (VS=SKS=KIS=I), but what we need is K. No, what you actually want to do is:
K=V(VVVVV)
Why's that? Well, how are we going to extract that K from λx.xKS? By duplicating it! SII=λx.xx, so one could do this by taking V(SII) to get KKS=K. But that uses up a lot of V's. Thing is, we can replace those I's with V's. Because, you see, VK=K (extracting the first element), thus SVV (or VVVVV) will work just as well as SII. And thus K=V(VVVVV). Yielding S in 3 and K in 6.
I'm pretty sure this is minimal, by which I mean with the help of an online "lambda calculator" (online since computer was down, you know) I checked all the 4-V and 5-V possibilities (or at least, I think I was exhaustive) and none of them worked.
Now I'm wondering how common such "universal combinators" are (guess: probably pretty common, however you measure it) and what the shortest one (measured however) might be. Not going to think about these things, though, this is really not stuff I know...
Addendum: Let's count length by "number of occurrences of variables, including right after a lambda", so e.g. I, K, and S have lengths 2, 3, and 7, while U and V both have length 12.
-Harry
