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 > <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. 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.
