8 ms·
Where Did Combinators Come From? Hunting the Story of Moses Schönfinkel
- dvt 6y agoI know Stephen Wolfram is a bit of a contentious figure, but his write-ups are always absolutely incredible. And if you're wondering why combinators are important (particularly S and K), SKI is a universal formal system[1]. Which is kind of crazy to think about: just two axioms and modus ponens can compute anything (I is just SKK). [1] http://people.cs.uchicago.edu/~odonnell/Teacher/Lectures/Formal_Organization_of_Knowledge/Examples/combinator_calculus/ http://people.cs.uchicago.edu/~odonnell/Teacher/Lectures/For...
- ignoranceprior 6y agoThere are actually single combinators which form a complete basis, i.e. from which you can get S and K, and thereby universal computation. https://en.wikipedia.org/wiki/Combinatory_logic#One-point_basis https://en.wikipedia.org/wiki/Combinatory_logic#One-point_ba... https://en.wikipedia.org/wiki/Iota_and_Jot#Universal_iota https://en.wikipedia.org/wiki/Iota_and_Jot#Universal_iota
- dvt 6y agoIota is still defined in terms of S and K. More technically, Iota is an "improper" combinator (see pg. 779 in [1]). Therefore, you can't axiomize Iota, so it would be hard to argue that it's more "fundamental" than S and K. [1] https://books.google.com/books?id=1xEVkzuX5e0C&pg=PA779&lpg=PA779#v=onepage&q&f=false https://books.google.com/books?id=1xEVkzuX5e0C&pg=PA779&lpg=...
- tromp 6y agoA single point basis (like X = \z. z K S K for which X X = K K, X X X = K, and X (X X) = S) is not in itself a combinator. A combinator is not just a closed lambda term; it must have all lambdas in leading position. Like S = \x \y \z. x z (y z)
- a1369209993 6y ago> A single point basis [...] is not in itself a combinator. > A combinator [...] must have all lambdas in leading position. What's your opinion on: ωabcd = bd(cd) if a has no normal form[0][1] or = c if b has no normal form or = d if c has no normal form or = dd otherwise where SII = ωωωω Ω = SII(SII) = ωωωω(ωωωω) S = ωΩ = ω(ωωωω(ωωωω)) K = ωωΩ = ωω(ωωωω(ωωωω)) I = ωωωΩ = ωωω(ωωωω(ωωωω)) as a single-'combinator' basis? 0: Aka, does not halt. 1: Evaluation diverges if a (or b or c, if queried) is somthing like: SII(C(C(B(ωωx(KI)K)(SII))Ω)I) (from https://en.wikipedia.org/wiki/Combinatory_logic#Undecidability_of_combinatorial_calculus https://en.wikipedia.org/wiki/Combinatory_logic#Undecidabili...) that tries to diagonalize ω.
- tromp 6y agoSuch a combinator ω cannot exist.
- Uzomidy 6y agoDoes this mean that the Y combinator, Y = λf.(λx.f (x x)) (λx.f (x x)), is not a combinator?
- deleted 6y ago[deleted]
- samizdis 6y agoThat's a fascinating piece, although IMO Wolfram could really do with an editor. While I realise that the article contains serious/important information (for mathematicians, historians, comp scientists etc), this bit resonated the most with me: Göttingen was at the time a top place for mathematics. In fact, it was a sufficient “math town” that around that time postcards of local mathematicians were for sale there. Utterly charming.
- artemonster 6y agoI can really recommend a book called „To Mock a Mockingbird“ on this topic. Full of deep dives, cool puzzles and such.
- carapace 6y agoI suspect Smullyan was one of those people who achieved enlightenment by pure reason. Consider "Planet Without Laughter" (note this from the site of Knuth-- that Knuth --and presumably he hosts it there for a reason, so pay attention kids!) https://www-cs-faculty.stanford.edu/~knuth/smullyan.html https://www-cs-faculty.stanford.edu/~knuth/smullyan.html Also he looks like Gandalf! :)
- leafmeal 6y agoNow what does it say about me if I read this whole thing and didn't find it all that funny?
- carapace 6y agoThere's no accounting for taste. I'm ashamed to admit my father didn't find the works of Douglas Adams funny. I loved him anyway. In any event, I don't think the piece is meant as a "ha ha" comedy. It's more of a contemplation or a work of philosophy. Did it make you smile at any point?
- 6y ago
- hanslub42 6y agoI thoroughly enjoyed this story, and Wolfram's thorough detective work For those interested, Schönfinkels article (über die Bausteine der mathematischen Logik) is available online [1]. A good writeup about its significance can be found in the Stanford Encyclopedia of Philosophy [2] [1] http://www.cip.ifi.lmu.de/~langeh/test/1924%20-%20Schoenfinkel%20-%20Ueber%20die%20Bausteine%20der%20mathematischen%20Logik.pdf http://www.cip.ifi.lmu.de/~langeh/test/1924%20-%20Schoenfink... [2]https://plato.stanford.edu/entries/logic-combinatory/#SchoElimBounVari https://plato.stanford.edu/entries/logic-combinatory/#SchoEl...
- taliesinb 6y agoIf video is more your thing, Stephen just wrapped up a long, interesting livestream about combinators, and the life of Moses: https://www.youtube.com/watch?v=PG2G5xSz0NQ https://www.youtube.com/watch?v=PG2G5xSz0NQ
- brodo 6y agoJust watched it live on twitch! There where some great people there for the Q and A.
- sideeffffect 6y agoReally amazing cast: Dana Scott, Phil Wadler, Barry Jay, last student of Curry (whose name I don't remember)... it's really interesting to see all these people together.
- breck 6y agoDownvote this dumb fanboy comment all you want, but just wanted to state for the record IMO we're gonna need a prize bigger than Nobel for Wolfram. This post is fantastic. So data rich, so detailed, it really puts you right there.
- breck 6y agoThere are so, so many rich sidenotes in this post. One I like: "Of course, there are confusions. There’s yet another birthdate for Schönfinkel: September 4, 1889. Wrong year. Perhaps wrongly done correction from the Julian calendar." Here we are over 100 years later and still dealing with constant time and calendar bugs.
- burakemir 6y agoThe article is a deep dive into Moses Schönfinkel's life, and mentions how his work is picked up by Haskell Curry. It is very long, contains surprisingly few of the characteristic Wolfram promotion usually found in Wolfram texts, but besides a detailed biography and pictures of historic documents, there are a few gems (people who researched "algebra of logic" before most others) for the persistent reader. > And maybe if the operation we now call currying needs a symbol we should be using the “sha” character Ш from the beginning of Schönfinkel’s name to remind us of a person about whom we know so little, but who planted a seed that gave us so much. That's a good suggestion! For folks who are interested in combinators but didn't get what they want from the text: the approachable reference on combinators is Hindley and Sheldon's "Lambda-Calculus and Combinators: an introduction" ... and of course, there is "To mock a mockingbird" by Raymond Smullyan, which introduces the topic through puzzles.
- burakemir 6y agoTypo: Hindley and Seldin ... silly phone autocorrect
- a-nikolaev 6y agoI wish Wolfram used help of a Russian-speaking editor, but the material makes up for the small errors he makes.
- perardi 6y agoThere are now some updates with improvements to the Russian-language bits. https://writings.stephenwolfram.com/2020/12/where-did-combinators-come-from-hunting-the-story-of-moses-schonfinkel/ https://writings.stephenwolfram.com/2020/12/where-did-combin...
- mikewarot 6y agoI've given an 101 minutes trying really hard to grok this... everything I've found skips the very basic definition of what S and K are for some astoundingly dumb reason. Stephen Wolfram obviously knows what he's talking about... but lacks Feynman's ability to put it into layman's terms. My suspicion is that there is an implied list, and if you go off the end of the list, you get a hidden zero... if not, you get a one. The SKI combinator Wikipedia page has a section about Boolean logic that comes close to making sense to me. Please let me know if I'm getting this right.... restating the page, putting it into familiar notation Booleans are a list of [1,0] T(x,y) = x F(x,y) = y Applying this over Booleans T(1,0) --> 1 F(1,0) --> 0 They then go to explain that T(x,y) = K combinator Then they go on to explain False(x,y) = SK, which I think is K(S(Boolean) It's at this point, I'm lost. Is SK --> S(K(xy)) or K(S(xy)) I can't resolve that to get any further.
- rraghur 6y agoTry this video of you haven't already https://youtu.be/pAnLQ9jwN-E https://youtu.be/pAnLQ9jwN-E
- mikewarot 6y agoI did... thanks for the link. I also went back and started watching the first part.
- dvt 6y agoThis is what S and K (and I) are: S := λx.λy.λz.x z (y z) K := λx.λy.x I := λx.x There's nothing really more to it. What's weird/amazing is that just with these three (technically, just S and K, as I can be derived from them), you can compute anything.
- mikewarot 6y agoI still don't understand the way this breaks down... How many parameters do S,K,or I take? If x=11, y=12, z=13 what are S,K? I assume I = 11
- galaxyLogic 6y agoRelated: There exists programming language Unlambda https://en.wikipedia.org/wiki/Unlambda https://en.wikipedia.org/wiki/Unlambda which is based on combinatory logic in which "Variables are unsupported". From a programmer's viewpoint it seems like a daunting task: Write all your programs without using variables. Can that work in practice?
- welder 6y agoWhy did Y Combinator the company choose their name? https://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator https://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combi...
- askthereception 6y agoFor those who are getting confused about the S and K combinators, another definition is implied by the notion of a 'partial combinatory algebra' [1]. It is a set A together with a partial map A x A -> A, viewed as 'application'. You then require the S and K combinators to exist somewhere in A (they are non-unique) and you can prove things like the recursion theorem. [1] https://ncatlab.org/nlab/show/partial+combinatory+algebra https://ncatlab.org/nlab/show/partial+combinatory+algebra
- choeger 6y agoFunnily, I do indeed know the name from a footnote that mentions he is the original inventor of currying.
- amazedww 6y agoWhat really amazes me is the favourable response of people. In hindsight, these are folks that either helped wolfram, interacted w him in the past or worked for him. On yet another tombstone, I wonder how many people internally within the wolfram dark net, touched this up Before it got published. The so called gem notes, are more often than not, not his own discoveries aka universality of rule 110. Truth be told I hear many other voices in this piece that have not been mentioned or acknowledged.