On Sun, Aug 5, 2018 at 2:05 PM Bruno Marchal <marc...@ulb.ac.be> wrote:
> Hi Jason,
>
>
> On 5 Aug 2018, at 05:24, Jason Resch <jasonre...@gmail.com> wrote:
>
>
>
> On Sat, Jul 28, 2018 at 2:19 PM Bruno Marchal <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.
>
>
Thank you. :-)
>
>
>
>
>>
>> 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.
>
>
Okay, I see.
>
>
>
> 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).
>
I believe B exists, given combinators are universal, but I don't know what
it is.
>
> 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)
>
Ahh here it is!
>
> 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.
>
Okay, I follow so far. The idea of waiting until having enough arguments
before activating is helpful and I think I was missing that before.
>
> 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?
>
It isn't fully clear to me how the "eliminate left parenthesis" rule works.
Is it that you only cancel the left-most parenthesis until you hot a
non-left-parenthesis element, or is it more complex than this?
>
> 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?
>
It is quite a long process to work out the steps from a seemingly simple
equation, but going step by step I can see how it leads to x(yz).
>
> 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.
>
Oh okay. I have to fight to overturn several decades of using parenthesis
in a different way, but I think I am getting there, slowly.
>
>
>
>
>
>
>>
>> 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).
>
"Living strings" is a helpful analogy in my mind.
>
>
>
>
>
>
>
>
>>
>> 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.
>
>
>
Okay.
>
>
>> 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.
>
>
Ha! Speaking of computer's imaginations, have you seen the "deep dreams"
images, creating by feeding random input into trained neural nets, and
permuting that input with the goal of increasing what the net is able to
recognize? Here are some examples:
https://www.google.com/search?q=deep+dreams&source=lnms&tbm=isch&sa=X&ved=0ahUKEwil4I33kMHdAhWH7oMKHcIGAskQ_AUIDigB&biw=1507&bih=847
>
>
> 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
>
>
>
>
Oh wow. :-)
>
>
>
>
>>
>> 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.
>
It has been very helpful. I intend to follow up with your subsequent posts
shortly.
>
> 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?
>
>
I am guessing it leads to an infinite recursion, infinite exponential
doubling, but that is just my intuition..
Jason
--
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.
