Hi Jason, Brent, others,
In this post, I sum up what we have seen so far, and provide the solutions to
the (suggested) exercise. Skip the solutions if you still want to find by
yourself.
The motivation is to better appreciate what is a computation, and why, when we
assume Mechanism, the two axioms Kxy = x and Sxyz = xz(yz) are enough, and
cannot be completed with other axioms, unless we describe observer (and not
“reality”).
------------
A combinator is a combination of S and K, i. e. S is a combinator, K is a
combinator, and from two combinators x y you can build the combinator (x y).
>From this you can enumerate already easily all combinators. K, S, (K K), (K
>S), (S K), (S S), ((K K) K), (K (K K)), …
Now, we use a convention to help the readability: we suppress the left most
parentheses (and their right corresponding parenthesis).
So
abc(def)ghu
can be be read as the combinator abc(def)gh applied to u. But abc(def)gh can be
seen itself as the combinator abc(def)g applied to h, and then abc(def)g can be
seen as abc(def) applied to g. Then abc(def) is abc applied to (def). abc is
ab applied to c: ((a b) c), and def is de applied to c.
You can also read from the left: in abc(def)ghu, it means a is applied to b: (a
b) and that is applied to c: ((ab)c) which is applied on (def), which is
((de)f), and the result of that is applied to g, and the result is applied to
h, and the result is applied to u.
With those conventions, the only two axioms, or laws, (besides some equality
rules) are that, with x and y being any combinators.
Kxy = x
Sxyz = xz(yz)
It means that the combinators K, when he get two arguments x y, it becomes
instable and reacts and gives x as a result.
S “reacts” only when he got his three arguments (in the “Curry” way: Sxyz is
really (((Sx)y)z), and that gives xz(yz): S applies x on z, and that is applied
on the result of applying y on z.
The expression Kxy and Sxyz are called redex, and a combinators is instable as
long as it contains redexes. When it does no more contain a redex, we say that
a combinator is in normal form (I use often “stable” also).
The computation are not deterministic. If a combinator contains two different
regexes, you can reduce them in any order. It can be proved that if the
combinator has a normal form, then all converging path will give the same
result (but we will see this is untrue if some path are infinite).
Summary: combinators are combination of K and S, and their have a sort of
dynamic provided by the two laws above.
The only difficulty is due to the explosion of parentheses, which is limited by
our convention of not writing the left parentheses when there is no ambiguity.
That can lead to a new difficulty, due to forgetting that those parenthesis are
still there. For example, let us compute:
KSxyz
x and y and z are just any combinators. Someone could wrongly claim that it
contains the redex Sxyz, and that it might reduces to Kxz(yz), and then x. But
that is incorrect. It would be correct if it was K(Sxyz). KSxyz gives (KSx)yz =
Syz, not x.
If you substitute the combinator ab for c in cxyz, you can write abxyz. But if
you substitute ab for x, that gives c(ab)yz. In that case the parentheses are
obligatory, as a(bc) is different from abc = (ab)c.
OK. Please ask question if anything seems unclear.
Let us see the combinators that we have already met.
Is there an identity combinator, i.e. a I such that Ix = x ? Yes I = SKK.
Indeed SKKx = Kx(Kx) = x. So SKK is the identity bird. Note that SKA is an
identity bird for any combinator A. Exemple SK(KK)x = Kx(KKx) = x.
Is there a combinator M such that Mx = xx ? Yes. Mx = xx = Ix(Ix) = SIIx, so M
= SII. Verification Mx = SIIx = Ix(Ix) = xx.
Is there a combinator f such that fxy = y ? Yes. f = KI. Verification fxy =
KIxy = (KIx)y = Iy = y. So KI is the projection on the second coordinate. Why
do I use the matter f for its name? Because later KI will play the role of the
constant propositional false. We will come back on this. Similarly K will play
the role of the truth constant t.
Is there a combinator B such that Bxyz = x(yz) ? Yes. Bxyz = x(yz) = (Kxz)(yz)
= ((Kx)z)yz) (I added left parenthesis to help seeing the matching with the
second S redex) = S(Kx)yz = ((KS)x(Kx))yz = KSx(Kx)yz = S(KS)Kxyz, so B =
S(KS)K. Verification: S(KS)Kxyz = KSx(Kx)yz = S(Kx)yz = Kxz(yz) = x(yz).
OK?
I suggested some “exercises”.
1) Is there a W such that Wxy = xyy ?
2) Is there a T such that Txy = yx ?
3) is there a L such that Lxy = x(yy) ?
4) is there a C such that Cxyz = xzy ?
The method consist is trying to introduce K and S, or other combinators already
defined, to match the right hand part of the regexes, and go backward.
Solutions: (you can skip this if you want take more time to find them.
Later, in "combinator 2”, I will give an algorithm to solve those problem.
1) Wxy = xyy = (xy)(Iy) = SxIy = Sx(KIx)y = SS(KI)xy, so W = SS(KI).
Verification: SS(KI)xy = Sx(KIx)y = xy(KIx)y = xy(Iy) = xyy
2) Txy = yx = y(Kxy) = Iy(Kxy) = Iy((Kx)y) = SI(Kx)y = B(SI)Kxy, so T = B(SI)K.
(B is handy to suppress the right parentheses). Verification: B(SI)Kxy =
SI(Kx)y
= Iy(Kxy) = yx
3) Lxy = x(yy) = x(My) = BxMy = Bx(KMx)y = SB(KM)xy, so L = SB(KM).
Vérification: Lxy = SB(KM)xy = Bx(KMx)y = x(KMxy) = x(My) = x(yy).
4) Cxyz = xzy
This one is a bit harder. xzy = xz(Kyz) = Sx(Ky)z = B(Sx)Kyz = BBSxKyz =
BBSx(KKx)yz = S(BBS)(KK)xyz, so C = S(BBS)(KK).
Vérification: S(BBS)(KK)xyz = BBSx(KKx)yz = B(Sx)(KKx)yz = B(Sx)Kyz = Sx(Ky)z
= xz(Kyz) = xzy.
OK? Take the time to understand well the verification. Ask any question if you
have some doubt at some steps.
Next post: the algorithm to solve this task. It helps to train oneself a bit
before.
Bruno
> On 5 Aug 2018, at 21:05, Bruno Marchal <marc...@ulb.ac.be> wrote:
>
> Hi Jason,
>
>
>> On 5 Aug 2018, at 05:24, Jason Resch <jasonre...@gmail.com
>> <mailto:jasonre...@gmail.com>> wrote:
>>
>>
>>
>> On Sat, Jul 28, 2018 at 2:19 PM Bruno Marchal <marc...@ulb.ac.be
>> <mailto:marc...@ulb.ac.be>> wrote:
>> Hi Jason, people,
>>
>>
>> Hi Bruno,
>>
>> Thank you for this. I've been trying to digest it over the past few days.
>
> No problem. It was hard to begin with , and I was about sending few easy
> exercise to help for the notation. But you did very well.
>
>
>
>>
>>
>> I will send my post on the Church-Turing thesis and incompleteness later. It
>> is too long.
>>
>> So, let us proceed with the combinators.
>>
>> Two seconds of historical motivation. During the crisis in set theory, Moses
>> Schoenfinkel publishes, in 1924, an attempt to found mathematics on only
>> functions. But he did not consider the functions as defined by their
>> behaviour (or input-output) but more as rules to follow.
>>
>> He considered also only functions of one variable, and wrote (f x) instead
>> of the usual f(x).
>>
>> The idea is that a binary function like (x + y) when given the input 4, say,
>> and other inputs, will just remains patient, instead of insulting the user,
>> and so to compute 4+5 you just give 5 (+ 4), that is you compute
>> ((+ 4) 5). (+ 4) will be an object computing the function 4 + x.
>>
>>
>> The composition of f and g on x is thus written (f (g x)), and a combinator
>> should be some function B able on f, g and x to give (f (g x)).
>>
>> Bfgx = f(gx), for example.
>>
>> So am I correct to say a combinator "B" is a function taking a single input
>> "fgx”,
>
> Three inputs. B on f will first gives (B f), written Bf, then when B will get
> its second input that will give ((B f) g), written Bfg, which is a new
> function which on x, will now trigger the definition above and give the
> combinator (f (g x)), written f(gx) and which would compute f(g(x)) written
> with the usual schoolboy notation.
>
>
>
>
>> but is itself capable of parsing the inputs and evaluating them as functions?
>
> It just recombine its inputs, the functions will evaluate by themselves.
> Don’t worry, you will see clearly the how and why.
>
> B is called an applicator, because given f, g and h has arguments, Bfgh, it
> gives f(gh). I have used f and g and h has symbol, but I can use x and y and
> z instead. Those variables are put for combinators. Bxyz = x(yz). Formally B
> only introduce those right parenthesis. With full parentheses we should write:
>
> (((Bx)y)z) = (x(yz)). But we suppress all leftmost parentheses: Bxyz =x(yz).
>
> The interesting question is: does B exist? Which here means —is there a
> combinator (named B) which applied on x, then y, then z, gives x(yz).
>
> Later I will provide an algorithm solving the task of finding a combinators
> doing some given combination like that. But here I just answer the question:
> YES!
>
> Theorem B = S(KS)K, i.e. Bxyz = S(KS)Kxyz = x(yz)
>
> Proof: it is enough to compute S(KS)Kxyz and to see if we get x(yz)
>
> Let us compute, and of course I remind you the two fundamental laws used in
> that computation:
>
> Kxy = x
> Sxyz = xz(yz)
>
> S(KS)Kxyz =
>
> OK let see in detail that is the combinator S, which got a first argument,
> the combinator (KS) this gives (S (K S)) written S(KS), which remains stable
> ("not enough argument”), then S(KS) get the argument K which gives S(KS)K,
> which remains stable (indeed it is supposed to be the code of B) and indeed S
> has still got only his first two argument and so we can’t apply any laws to
> proceed, but now, S get its third argument x so
>
> we are at S(KS)Kx, that is S (KS) K x, and here S has three arguments and so
> match the left part of the second law S x y z, with x = KS, y = K and z = x.
>
> Now the second law is triggered, so to speak, and we get xz(yz) with with x =
> KS, y = K and z = x, and that is gives (KS)x(Kx) = KSx(Kx). OK?
>
> You always add the left parentheses, or some of them to be sure what we have
> obtained. KSx(Kx) = ((KSx) (Kx)), but “KSx” is a redex, as it match Kxy, with
> x = S and y = x, and so get “reduces” into S, so we get S(Kx) (starting from
> S(KS)Kx, which is Bx, waiting now for y and then z.
>
> We are at Bxy = S(KS)Kxy = (we just computed) S(Kx)y, which is S with “not
> enough argument” so we give the remains z and get
>
> S(Kx)yz
>
> Which triggers again the second law to give (x = (Kx), y = y, z = z)
>
> (Kx)z(yz) = Kxz(yz)
>
> And again, Kxz gives x (by the first law) so we get
>
> x(yz).
>
> OK?
>
> How could we have found that B was computed by the combinators S(KS)K?
>
> We can do this by guessing and computing in reverse, introducing K or other
> combinators so that we can reverse the fundamental laws. So in x(yz), we can
> replace x by (Kxz) that is ((Kx)z) so that we can apply axiom 2 to x(yz) =
> (Kxz)(yz) = S(Kx)yz, then, well the “yz” are already in the good place, but
> the x is still in a parenthesis which has to be removed: we just do the same
> trick and replace S(Kx) by (KSx)(Kx), and so we get S(KS)Kx and we are done:
> B = S(KS)K.
>
> Don’t worry too much, I will soon or a bit later provide an algorithm which
> from a specification Xxyzt = xt(ytxzx) find a combinator X doing that task.
>
> To summarise the computation:
>
> S(KS)Kxyz
> = KSx(Kx)yz
> = S(Kx)yz
> = (Kxz)(yz). (In passing Here we use that S is an applicator)
> = x(yz)
>
> Each reduction of a redex (“Kxy” or “Sxyz”) counts as one computational step.
>
>>
>>
>> When I said that Shoenfinkel considered only functions, I meant it
>> literally, and he accepts that a function applies to any other functions, so
>> (f f) is permitted. Here (f f) is f applied to itself.
>>
>> So are input and output values themselves considered as functions, with
>> fixed values just being identities which return themselves?
>
> Yes, you can see all combinators as function of one argument. Take K for
> example. The first law says Kxy = x. Typically you can interpret K as the
> projection on the first coordinate: you give (x y) and it outputs x. But K is
> also a function of one argument (K x) is the constant function x.
>
> Ley us train ourself with computing the first combinators made only of K.
>
> We must compute K. Obviously, it has not enough argument, so that gives K
> (and that stops!). We stop when the combaintors has no more regexes, that is,
> an occurence of the pattern Kxy or Sxyz.
>
> KK = ?
>
> Well, KK gives KK. It is a function, as KK is the constant K. KKS = K, KK(SS)
> = K, KKK = K for all x, by the first law.
>
> KKK = ?
>
> Well, that gives K, in one computational step, by the first law (of course
> without S only the first law applies).
>
> KKKK = ? That is (KKK)K, and that is KK.
>
> From this you can guess (and prove by induction) that KKKKKK…K with an odd
> number of K will give K, and with an even number of K will give KK.
>
> K(KK) = ?
>
> Hmm… here K got only one argument (and the difficulty for some will be in not
> using the schoolboy meaning: K(KK) is not K applied to two arguments (K, K),
> but is K applied to the (stable) combinator KK. Now K need two argument for
> the first law to be triggered, and so K(KK) remains stable.
>
> K(KK)K = ?
>
> That gives (KK) = KK by the first law.
>
> What gives (KK) applied to (KK)?
>
> Beginners get easily wrong on this one, presented in this way! They think
> that each KK is stable, and that this cannot evolve.
> Nervetheless, In full parentheses notation, ((K K) (K K)) does match ((K x)
> y), with x = K and y = (K K) = KK, so that gives K. But it is even clear with
> the convention to eliminates all leftmost parenthesis and their match. KK
> applied to KK is KK(KK), with match clearly Kxy, with x = K and y = KK, so
> KK(KK) = K.
>
>
>
>>
>>
>> A first question was about the existence of a finite set of combinators
>> capable of giving all possible combinators, noting that a combinators
>> combine. Shoenfinkel will find that it is the case, and provide the S and K
>> combinators, for this. I will prove this later.
>>
>> A second question will be, can the SK-combinators compute all partial
>> computable functions from N to N, and thus all total computable functions?
>> The answer is yes. That has been proved by Curry, I think.
>>
>> OK? (Infinitely more could be said here, but let us give the mathematical
>> definition of the SK-combinators:
>>
>> K is a combinator.
>> S is a combinator.
>> If x and y are combinator, then (x y) is a combinator.
>>
>> That is, is combinator is S, or K or a combination of S and K.
>>
>> So, the syntaxe is very easy, although there will be some problem with the
>> parentheses which will justified a convention/simplifcation.
>>
>> Example of combinators.
>>
>> Well, K and S, and their combinations, (K K), (K S), (S K), (S S), and the
>> (K ( K K)) and ((K K) K), and (K (K S)) and …… (((S (K S)) K) etc.
>>
>> I directly introduce an abbreviation to avoid too many parentheses. As all
>> combinator is a function with one argument, I suppress *all* parentheses
>> starting from the left:
>> The enumeration above is then: K, S, KK, KS, SK, K(KK), KKK, K(SK) and …
>> S(KS)K ...
>>
>> So aaa(bbb) will be an abbreviation for ( ((a a) a) ((b b) b) ). It means a
>> applied on a, the result is applied on a, and that results is applied on ..
>> well the same with b (a and b being some combinators).
>>
>>
>>
>> OK?
>>
>> The syntax is a bit unfamiliar to me but I think I follow so far.
>
>
> Yes, the notation takes some time to get familiar with. It is normal.
>
>
>
>>
>>
>> Of course, they obeys some axioms, without which it would be hard to believe
>> they could be
>> 1) combinatorial complete (theorem 1)
>> 2) Turing complete (theorem 2)
>>
>> What are the axioms?
>>
>> I write them with the abbreviation (and without, a last time!)
>>
>> Kxy = x
>> Sxyz = xz(yz)
>>
>> That is all.
>>
>> A natural fist exercise consists in finding an identity combinator. That is
>> a combinator I such that Ix = x.
>>
>>
>> I am having trouble translating the functions and their arguments (putting
>> the parenthesis back in), is this translation correct?
>>
>> K(x(y)) = x
>> S(x(y(z))) = x(z(y(z)))
>
>
> It is
>
> ((Kx)y) = x
> (((Sx)y)z) =((xz)(yz))
>
> You “currified” the combinators in the wrong direction. Think about xyztr as
> x waiting for y (x y) waiting for z ((x y) z) waiting for ...
>
> KKK = ((KK)K) = K
> K(KK) = well, it remains K(KK). It is (K(K K)) with full parenthesising.
>
>
>
>
>>
>>
>> Well, only Kxy can give x, and Kxy does not seem to match xz(yz), so as to
>> apply axiom 2, does it? Yes, it does with y matching (Kx), or (Sx).
>> (Sometime we add again some left parenthesis to better see the match.
>>
>> So, x = Kxy = Kx(Kx) = SKKx, and we are done! I = SKK
>>
>> Vérification (we would not have sent Curiosity on Mars, without testing the
>> software, OK? Same with the combinators. Let us test SKK on say (KK), that
>> gives SKK(KK) which gives by axiom 2 K(KK)(K(KK)) which gives (KK) = KK,
>> done!
>>
>> Note that SKK(KK) is a non stable combinators. It is called a redex. It is
>> triggered by the axiom 2. The same for KKK, which gives K. A combinators
>> which remains stable, and contains no redex, is said to be in normal form.
>> As you can guess, the price of Turing universality is that some combinators
>> will have no normal form, and begin infinite computatutions. A computation,
>> here, is a sequence of applications of the two axioms above. It can be
>> proved that if a combinators has a normal form exist, all computations with
>> evaluation staring from the left will find it.
>>
>> This seems reminiscent of a part of Gödel, Escher, Bach, where he was
>> describing univerality (or maybe it was proof systems), in terms of string
>> manipulation? Is this the spirit of combinators? Manipulating strings
>> through operations that parse (K), or re-arrange (S), and through any
>> combination of K and S can map any input string to any other?
>
>
> It is not really strings, as the combinators (x y) are better seen as the
> result of the application of some function/combinators x to some function
> combinators y.
> Combinators are very liberal, you can apply any combinators on any
> combinators. And they are both “programs” and “data”. Combinators combine,
> mainly, but (x y) might evolves if xy contains redexes (Kxy, or Sxyz). It is
> more like living strings. (And that will at some point shows that they are
> not good for the string manipulation, that we usually want to be static
> object, except for my type writer which correct my typo errors).
>
>
>
>
>
>
>>
>>
>> I will tomorrow, or Monday, show that there is a combinator M such that Mx =
>> xx, a combinators T such that Thy = yx,
>>
>> What is "x" here when it is not defined? Is it meant to represent some
>> arbitrary constant that depends on T?
>
> x and all variables represent some arbitrary combinators. The law Kxy = x,
> means that for all combinators x and y (Kx)y = x. A bit like the law x + 0 =
> x means that any number added to 0 gives that same number.
>
>
>>
>>
>> a combinator L such that Lxy = x(yy), … and others, Later, I will prove
>> theorem 1 by providing an algorithm to build a combinator down any given
>> combinations.That will prove the combinatorial completeness. Then I will
>> prove that all recursive relation admits a solution, i.e. you can always
>> find a combinator A such that Axyzt = x(Atzz)(yA), say.
>> Then I will show how easy we can implement the control structure IF A then B
>> else C, and follow Barendregt and Smullyan in using this to define the
>> logical connectives with combinators, then I will provides some definition
>> of the natural numbers, and define addition, multiplication, all primitive
>> recursive function, and then the MU operator, which is the while and which
>> will make easy to get Turing universality.
>>
>>
>> Interesting. I have trouble imagining how to construct a while loop from S
>> and K at this time. I am interested to see it.
>
>
> I will be able to show rather quickly how to implement the if then else. That
> is incredibly beautiful, and that provides a shortcut to implement logic.
>
> For the MU operator, I will need “recursion”, and that is also rather
> beautiful. Now, the MU operator itself is not that much of a beauty, and you
> will have to be slightly patient.
>
>
>>
>> I let you digest all this. You can try to Sind some combinators, or to apply
>> some random combinators to sequence of variable.
>>
>> It helps me to understand to implement something in software. If I were to
>> implement a simulation of processing S and K, is the idea to simply
>> represent the values of the functions as strings, or is that not sufficient?
>> For example, the input string "Kxy" returns "x", and the input string
>> "Sxyz" returns "xz(yz)" -- what does the added parenthesis here do? Is this
>> not the same as "xzyz”?
>
> For readability we suppress all leftmost parentheses. But we cannot suppress
> the right because it becomes ambiguous, as you should realise with the
> computation above. ((KK)K) = KKK = K, but K(KK) just remain quietly itself
> K(KK), because that match only Kx with x = the combinator KK. So K(KK) is
> waiting for a second argument. For example K(KK)S = KK.
>
>
>
>
>
>>
>>
>> A (difficult) question: would you say that SK = KI? That are different
>> combinators in normal form, but SKx remains normal, where KIx is trigged
>> immediately and give I. Yet, SKx computes the same function as I, (verify)
>> so?
>>
>> Doesn't S require 3 inputs? How does SKx function, does it assume the
>> expanded SKx = SKxy = Ky(xy)? But this equals "y" does it not?
>
> Let us compute both SK and KI on K (using Ix = x).
>
> (SK K) = SKK gives, well it remains itself as S needs its three arguments for
> using the second law.
>
> (KI K) = KIK = I, by the first law.
>
> Verdict: SK and KI are different, as there is a combinator x such such that
> SKx is different from I. Indeed SKK.
>
> Oh! Wait we have seen that I = SKK (let us verify this quickly:
>
> SKKx
> = Kx(Kx) by the second law
> = x by the first law.)
>
> So SK and KI are equal, after all. We will come back on this. By default we
> will say that two combinators are equal when they do the same things. In some
> more intentional context, we can adopt a weaker identity, and decide that SK
> and KI (which is K(SKK) are not equal.
>
>
>>
>> I will say that they are indeed equal, but this illustrates some other, less
>> extensional, and more intensional, definition of equality.
>>
>> By being Turing universal, the combinators give a complete universal
>> programming language. We will meet its cousin, the lambda terms, and some
>> descendants, like LISP.
>>
>> Is the distinction you are making here of whether functions are identical if
>> their outputs for the same input are identical,
>
> That is extensional equality that I will use by default. Smullyan does that
> also.
>
>
>
>> as opposed to functions are identical IFF they implement the same
>> intermediate computations/operations in the course of their evaluation?
>
>
> Yes, sometimes we want weaken the extensional criteria, to compare more the
> computations than the combinators, indeed. As you can guess, there are many
> options. The nice thing is that those option can be formalised by combinators
> identities, a but like adding the axiom SK = K(SKK) (i.e. SK = KI).
>
>
>
>
>
>
>
>>
>>
>> I have not allowed Smullyan,
>
> I meant (followed).
> (My computer is in the mode, if not the mood, to correct all my typo errors,
> but it has too much imagination, and with combinators, he always wrote “key”
> when I type “Kxy”, and when I type “Sxyz” he corrects me without saying and
> wrote “sexy” ! Lol.
>
>
>
>> and I have given what he called “The secret” (the combinatorial completeness
>> of S and K). I hope I have not spoiled too much your reading of “To Mock a
>> Mocking Bird”. The mocking bird is the bird M such that Mx = xx. Can you
>> find it? Hint: xx = Ix(Ix) which match axiom 2. We can of course use
>> combinators already defined, but it just abbreviates the normal expression
>> SKK,
>>
>> Hmm, so the problem is getting a set of combinators which outputs the same
>> string twice. I notice S takes in one "z" term and produces two of them, so
>> I think it has something to do with the "z" term of the S combinator. Then
>> the K combinator can be used to eliminate x and y, or perhaps using I.
>
> Good start!
>
>
>>
>> I am thinking something like: SII which would be S(SKK)(SKK)x, but I don't
>> know if this is right or if it is what you are looking for..
>
> Good arrival!
>
> Yes, the infamous Mocking Bird, the M which mimics all bird x on themselves
> is indeed given by SII, which is indeed S(SKK)(SKK), but without the x, which
> would be the argument.
> Why don’t you verify? Mx must give xx, so let us try SIIx. that gives Ix(Ix)
> by the second law, which gives xx.
>
> Of course we can also verify without using the macro I.
>
> S(SKK)(SKK)x =
> (SKKx)(SKKx) =
> (Kx(Kx)(Kx(Kx))
> xx
>
>
>
>
>>
>>
>>
>> Other very difficult exercice, can the physical reality truly implement K?
>> (Hint Hawking).
>>
>> Is this asking the question of whether information can be destroyed (as K
>> discards information)?
>
> Yes.
>
>
>
>>
>> Thanks for this. It has done a lot to demystify what the combinators are,
>> even if I still don't have an intuitive understanding of how to solve
>> problems or implement functions from them yet.
>
> That will come very soon. Tell me if this post has helped.
>
> In the next post, I will present you with other combinators, and you can
> meditate on how to find the combinators W, L, T and C, which are such that
>
> Wxy = xyy
> Lxy = x(yy)
> Txy = yx
> Cxyz = xzy
>
> W and L are duplicators, but L is a bit of an applicator too. T and C are
> permutators. You can of course use the combinators B, I, and M, as we have
> already found them. I guess C is a bit harder.
> Note that S is both a duplicator (some variable/imputs are duplicated), and
> an applicator: it introduce some right parenthesis.
>
> Also, a last question. Why is the mocking bird so infamous? What happens if
> we mock a mocking bird? Can you compute MM?
>
> Best,
>
> Bruno
>
>
>>
>> Jason
>>
>>
>> Anyone can ask any question.
>>
>>
>> Bruno
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Everything List" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to everything-list+unsubscr...@googlegroups.com
>> <mailto:everything-list+unsubscr...@googlegroups.com>.
>> To post to this group, send email to everything-list@googlegroups.com
>> <mailto:everything-list@googlegroups.com>.
>> Visit this group at https://groups.google.com/group/everything-list
>> <https://groups.google.com/group/everything-list>.
>> For more options, visit https://groups.google.com/d/optout
>> <https://groups.google.com/d/optout>.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Everything List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to everything-list+unsubscr...@googlegroups.com
> <mailto:everything-list+unsubscr...@googlegroups.com>.
> To post to this group, send email to everything-list@googlegroups.com
> <mailto:everything-list@googlegroups.com>.
> Visit this group at https://groups.google.com/group/everything-list
> <https://groups.google.com/group/everything-list>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
