Introduction to Combinatory Logic – #SoME2

This is Alexander Farrugia's and Giorgio Grigolo's submission to the second 3blue1brown Summer of Math Exposition.

#some2 #mathematics #combinators #logic

Music: Icelandic Arpeggios – DivKid

[charlesrosenbauer]

As far as displaying large combinator systems goes, it would probably be easier to appreciate their structure if drawn as a tree as opposed to with tons of nested parentheses.

[paskoolio]

The single combinator from which S and K can be defined goes well beyond Baker. I was a student of Corrado Boehm in 1985 (from Boehm trees in lambda calculus) and he taught us about the single combinator in 1985... This video reminded me of his fantastic lectures on combinatory logic, thank you.

[GuyMichaely]

9:30 Why does [I]_x become KI and not K? the second bullet applies and it does not say to append I

[jonaskoelker]

Very nice presentation, thank you.

A suggestion for future videos: when you show some kind of process, e.g. the SKIBC rewrite/translation, it would be really nice if all previous steps were shown along with the current step, e.g. with an additive/accumulative animation.

That way, I could compare steps n and n+1 which would help me understand what the rules mean and how to apply them.

[caselbravo]

Fantastic work thanks to everyone involved ! 🕊️

[msolec]

Nice. I had this book by R. Smullyan that explained this with birds. It was cool. This is a very explanation of the subject. Trying to find out how to get [OR]xy, [AND]xy. And maybe others, but with either of those you get NOR or NAND, and those are universal.

[EvanMildenberger]

Since the iota program at the end as a string of nested `i` literals, it could be represented as a syntax tree. And since there are no other semantics other than the syntax itself, that unique tree structure is the representation of the fibonacci sequence, it implies that anything isomorphic to that specific tree is the same as the fibonacci sequence. So the message that constitutes "the fibonacci sequence" is like an equivalence class with all possible representations of from that class being the same message. It's a deep idea that unites philosophy, math, linguistics and computer science!

[lexinwonderland]

yeah, this went WAY over my head, but it gets an upvote anyway cuz it's awesome and obviously brilliant. great job on the video!

[itsmeagain]

I can realise how much you have put your hearts and souls in this video, truly a hidden gem that should get millions of people to watch!

[DumblyDorr]

Effectively, combinatorial logic with only the iota-operator shifts most of the "work" to the order of evaluation and its manipulation (for a single rewrite rule). To get other combinators from iota, you force nested lazy evaluation of self-application on the right... it's amazing to think what can be expressed mostly with judicious application of parentheses (ask any LISP/Scheme programmer 😄).

[academyofuselessideas]

Excellent! Do you have something new in the works?

In one of the comments you mention "to mock a mockingbird" which is the classic book about combinators, but your presentation seems more modern and focused on the application to computation. It would be nice to know what references you used... it would be also nice to see how this compares to the lambda calculus, or how combinators and lambda calculus are the same...

Also the argument is that any computation can be done using combinatory logic but the proof is not obvious (although the result is believable as yet one more example of the church turing thesis)... the fact that one can achieve turing completeness with such simple systems make one wonder whether this has something to do with the basic structures of life. Perhaps the laws of physics build simple systems like combinators, which evolve into what we call life...

[DerMathematicker]

8:58 Is it realy [f]_x -> K or is it [f]_x -> kf?

[andres_pq]

I love this video but I don't understand it. I will try to reproduce it by hand.

[synaestheziac]

0:52 did I see a subliminal Hilbert in there?

[eugenemosh]

27:43 -- impressive!! Only two symbols and () and Fibonachi encoded!

[rshell]

At least first 14 minutes doesn't tell how to verify that stuff works. For example 1:51 in video says KIxy reduces to y. Can I verify it? Or is it just by definition? Why it's not K(Ix)y -> Kxy -> x?
At time 3:00 "we have written program" what it does? "This is how combinators logic avoids variables altogether". We write x, y everywhere, isn't it variables? "Our program is simply string of combinators" Well, isn't Ix reduces into x? Isn't program "x" then?
Summary: in my opinion this video is very.... very confusing.

[MagicGonads]

Since you only need one symbol (iota) coupled with two grouping symbols (parentheses), you can represent a program using instructions that only take two bits each, with a value left over. Then if you want to support side-effects, do a UTF inspired 'if the chunk is 11 then load another chunk to extend the code' for whatever side effects you wanna add to your architecture/CPU. Though maybe we need a proper padding instruction (usually nop or int 3)

[sabriath]

That bonus bit reminds me of whitespace programming language

[skilz]

Next up, an FFT and its Inverse Algorithm using only Combinatory Logic followed by The Wave Collapse Function.

[霍金本人]

But why a slash in the iota combinator only mode?