วีดีโอ

KIxy=(KIx)y=Iy=y

@epgui Part of the confusion arises because they didn't explain how combinators associate... so, it is not clear if one should think of KIxy as (((KI)x)y) or as K(I(x(y)). The way you associate things in this context matters... When working with combinators, the convention is to associate to the left, so Kxy->x would be more pedantically be written as ((Kx)y)->x... Based on that observation KIxy = (((KI)x)y) -> Iy -> y... A fun book about this is "to mock a mockingbird" by Smullyan... they mention that book in one of the comments... Working with combinators take some practice

In simple words, the First symbol is applied first always (lazy evaluation). And since K takes the 2 objects in front of it and becomes the first one, ignoring anything else (KIx -> I)..So KIxy -> Iy -> y.

@@Bobby_101 Nice explanation!

​@@Bobby_101 In other words, everything is implicitly left-associative, and symbols representing functions are treated the same way as symbols representing values? That seems a bit weird syntactically, but if that's the rule then that makes sense.

​@@academyofuselessideas Thanks. @epgui Yah it's a bit odd at first, just roll with it to see what results it brings.

@DeclanMBrennan The iota combiator together with the machinery to interpret it is turing complete (this is like saying that not only you need a program but also a compiler that runs the program)... that sounds mind blowing but then you realize that there are a bunch of things that are turing complete...I believe that so far, the smallest turing complete machine Wolfram 2-state 3-symbol turing machine... this is interesting because it kind of hints that we can get that type of computation with very simple systems, which kind of leads to how intelligence and life are plausible (the argument is that something as simple as the wolfram 2-state 3 symbol machine is simple enough that it could have happened by chance without any intelligent designer)

@@academyofuselessideasI was using "Turing complete" in the sense of a "Turing complete language" but that's a fair point. Thanks for mentioning the Wolfram TM- looking forward to reading up on it. I believe Conway's Game of Life may be Turing complete as well and somebody with way too much free time made hardware within Game of Life to execute its own Game of Life - a cool example of a simulation within a simulation.

@@academyofuselessideas I just had a quick look at your wonderful channel which I didn't know existed. I feel like a kid in a mathematical sweet shop. 🙂

@@DeclanMBrennan Game of life inside game of life sounds pretty cool... The observation that there are many simple turing complete machines is also part of Wolfram's argument that all physics are automatas (kind of like what we observe is some sort of emergent phenomena caused by very tiny automatas)... I like the philosophy behind some of those ideas but I don't know enough about them to give an informed opinion though

@@DeclanMBrennan I am glad to have you on board!

It would be nice to see it in action in a similar way to the legendary post "to dissect a mockingjay".

​@@jackozeehakkjuz I could not find that post? Are you referring to the book, to mock a mockingbird?

@@vyrsh0 Sorry, yes. To mock a mockingjay is a 1985 book by Raymond Smullyan. However, my intention was to point to the 1996 post by David Keenan called "To dissect a mockingjay", which is partly based on Smullyan's book. I hope you can find it now. I already edited my original comment to fix this mistake.

@@vyrsh0 I tried to post the link here a couple of times but I think youtube keeps deleting it.

@@jackozeehakkjuz yes I found "To dissect a mockingjay" can I ask you a question? where are combinators usefull? I've heard about them from people in lambda calculus as a way to make a tiny turing complete machine. and from APL users who use combinators in some practical way I dont know how?

@samytamim2603 @samytamim2603 awww... that happens with some math explanations... in my experience, it is best not to think to much about the math that makes you feel dumb and instead focus on the math that you enjoy and understand... even professional mathematicians have no idea of what other mathematicians are doing in a different field... Combinators can be fun but they are somehow esoteric anyways... just do what you find fun!

@@academyofuselessideas I actually got the Ahaaa moments, then got shocked knowing I was missing out these stuff. It was a bit sarcastic xD

@@samytamim2603 now I feel dumb 🙃

@@academyofuselessideas 😆

You're welcome!

It is because other combinators can be expressed in terms of S and K alone, for example: I = SKK (1) B = S(KS)K C = S(BBS)KK where C can be written using (1) as C = S((S(KS)K)(S(KS)K)S)KK and so on...

Not an expert in this either but it's a mix of both. The first few stuff tells us how notations work. Kinda like the PEMDAS of combinatory logic. So if you have KIxy, it is a signal for you to evaluate it as K(I, x) then y K(I, x) -> I. Then I(y) since I takes in one argument.

Agree. I don't get how KIxy reduces to Iy. It would help if precedence/order is shown. My initial understanding was: KIxy K(Ix, y) K(x, y) y But apparently it should be Iy?

@@padawanrl8834 I is an element that can be passed as the first argument to K by itself, can just group Ix together as the first argument of K. K I x y (K I x) y I y y

"This is how combinators logic avoids variables altogether". We write x, y everywhere, isn't it variables? Yes you write variables like x y and/or n when defining the behavior of combinators, but he provided around 9:00 the steps to refactor out the input variables using the combinators such that all you are left with is a composition of combinators where you arguments like x and y are impicit at the end of the function, making it "pointfree". A programming example of this using haskell would be: increaseByOne x = 1 + x can also be written as increaseByOne x = (1+) x increaseByOne = (1+) where you can remove the x and it is implicitly at the end. the beauty of combinators is that any expression with arguments can be refactored to be expressed as a pointfree (no reference to arguments) composition of basis combinators where the arguments are implicit at the end

@antoniolewis1016 Same opinion here... it would have been nice if they had mentioned that combinators associate by default to the left, so KIxy is shortcut for ((KI)x)y

hahaha... this brings an important point that is often left out in these type of results... many things are turing complete but computer languages are not only about producing computations but about making it easy for humans to express those computations... combiators are interesting for what they say about the nature of formal languages but they are probably not going to replace any real world programming language any time soon (though functional programming is valid and useful but even pure programming language go beyond implementing combinators)

Are you in the SoMe2 Discord? We could discuss there.

​@@alexanderfarrugia9299 Yes, will be trying to contact you soon

@@theunknown4834 I am farrugiamaths there. Message me even if I'm offline and I'll get back to you when I am. :)

@@alexanderfarrugia9299 Already did :>

@@alexanderfarrugia9299 I finished my implementation and uploaded it on GitHub and sent it to you :)

g could be a function though. Nothing wrong with being so.

@@xactxx everything is a function in combinator logic. The naming is about the intended usage

@@user-tk2jy8xr8b and what is the intended usage?

@@xactxx to be applied to anything or not on the right-hand side of the definition

@@user-tk2jy8xr8b fair enough. The reason why we used fgx is for consistency with the variables used for B and S. Essentially, B and C are the two halves of S, and using the same variables for S, B and C drives home this point.

One would first need to represent integers (for example, as a pair of naturals with appropriately defined operations), then move on to define rationals, as pairs of integers. Then reals could be defined using infinite lists. This video did not define lists (we didn't need them for our Fibonacci program) but lists may also be defined in terms of combinatory logic.

@@xactxx This topic is scary lol, still won't stop me from writing it in python

@@theunknown4834 I have a working implementation of the constructs in this video. It works, though very slowly, as is expected. But it works.

@@theunknown4834 writing this in python seems like a nice challenge, if you want a language that can evaluate these combinators with less of a hassle (and builtin lazy evaluation!) I would highly recommend Haskell.

Thank you!

That's because it's explained in the most complicated way possible. If he just wrote the lambda calculus notation it would be really simple