Why functions are turing complete (Lambda Calculus)
Ғылым және технология
Functions are an extremely useful part of programming, but it turns out that they're all you need to calculate anything. No data types, no control flow, just simple functions.
This is possible by using lambda calculus, a programming language and model of math invented by Alonzo Church in the 1930s which is capable of any computation with only one feature: the function.
Пікірлер: 232
Ow my brain
@aydynx
Жыл бұрын
really simple to understand if you have some background on cpu architecture and logic gates
@whannabi
Жыл бұрын
facts
@CMDRunematti
Жыл бұрын
@@aydynx im not even sure if this was programming, math, or what... and how did i get here...
@user-pr6ed3ri2k
Жыл бұрын
on
@natsudragneelthefiredragon
Жыл бұрын
@@user-pr6ed3ri2k off?
Thus solving the hardest problem in software engineering - naming things.
@AByteofCode
Жыл бұрын
How so?
@AshesOfEther
Жыл бұрын
@@AByteofCode It's a saying that the hardest problem in computer science is naming things, because it can be really hard. If you can't assign stuff, there's nothing to name
@orterves
Жыл бұрын
@@AByteofCode just a tongue in cheek joke. Have you heard, "There are only two hard problems in computer science - cache invalidation, naming things, and off by one errors"
@AByteofCode
Жыл бұрын
@@AshesOfEther ooh i see lol, nice one
@AByteofCode
Жыл бұрын
@@orterves yep, one of my favorite cs jokes
You can write the halting problem proof in lambda calculus by showing that a function that determines if another function will ever reach a fully reduced form leads to a contradiction.
@AByteofCode
Жыл бұрын
:o truttle! Also yeah, seems to make sense. I love how simple so many things are in lambda calculus lol
@Tabu11211
Жыл бұрын
@@yt45204 that needs to be a yt series
@orangenostril
Жыл бұрын
@@Tabu11211 a YT series
Sorry for the long wait, I was in Norway. As usual, what did you and what did you not enjoy in the video, please be honest with me so I can make better content for you guys!
@aaravbhatt760
Жыл бұрын
Ok, so this is a great video once u understand it - I learned how data types can be represented as functions, but I needed to try stuff out on a whiteboard to understand it. Maybe add examples on why something works or doesn't. (I was wrong before, here in my question)
@AByteofCode
Жыл бұрын
@@aaravbhatt760 the half assed assignment you can do is very limiting with scope, and so in your example there f x would not be able to reference a, so it wouldn't work. remember its less assignment as just humans naming patterns so we can simplify using the system
@aaravbhatt760
Жыл бұрын
@@AByteofCode I think I just understood it now, makes sense. I've been learning Haskell, and was confused why u can do that in Haskell. But then, does that mean Haskell isn't fully based on lambda calculus as we can name functions?
@AByteofCode
Жыл бұрын
@UC4Qih8jTMfBcmVxV98RnNnw Haskell is a lot more complex than lambda calculus, which is the BARE minimum you need to work. In lambda calculus, a function is simply a value that has to be defined using only what is in its scope. This means that the "variable" containing the function value is outside of the scope of the function, and so cannot be referenced by it.
@aaravbhatt760
Жыл бұрын
@@AByteofCode Got it, good explanation
This video: Explains lambda calculus. What my brain gets: *S U C C*
I never fully understand your video but still, it's short and I like it.
@user-zu1ix3yq2w
Жыл бұрын
Boolean algebra
I like to call λ calculus an unintentional esolang
@AByteofCode
Жыл бұрын
I totally agree lol
Loving the new mic quality, and your content is both educational and entertaining. Keep it up!
@AByteofCode
Жыл бұрын
Thanks man! Shall do :)
Really enjoy your videos. I think one way you could improve at the moment is your timing of visuals. Some things stay on the screen too short, or the animations/text are arranged in a way that I am not able to pick up on the message very easily. I find myself pausing and reminding in order to see what I missed. These are rather complex topics though, so I understand its not trivial to get the right pacing/level of detail.
@AByteofCode
Жыл бұрын
100% everything you said! I think I try maximizing my production value so much the content loses out on value. With school starting up, I'm gonna be scaling down the complexity of videos and hopefully the pacing is gonna get better, especially with time. One thing that could be helpful (but don't feel forced to) would be if I had timestamps of where the pacing was irritating, so I can learn from that!
@marcolerena456
Жыл бұрын
36s - 50s was particularly hard to follow.
@AByteofCode
Жыл бұрын
@@marcolerena456 Gotcha! I'll analyse that scene to try to figure out what went wrong so I can improve for next time!
@SebastianLopez-nh1rr
Жыл бұрын
Man, agree, I easily paused more than ten times. Maybe it could have been easier if you explained the fundamental concept and syntax a bit more. The python example for a function with multiple arguments was really helpful to decipher a bit of the syntax.
@AByteofCode
Жыл бұрын
@@SebastianLopez-nh1rr I see, comparisons to real code helps. I'll keep that in mind!
Awesome! Can't wait for the y-combinator video. I've implemented my own lambda calculus evaluator, but I've never gotten the Y combinator to work correctly... probably because I forgot about lazy evaluation :)
@AByteofCode
Жыл бұрын
Sounds like that could be it. Good luck with that evaluator!
@aioia3885
Жыл бұрын
you can use the Z combinator to do recursion in a language that implements strict evaluation order you don't even need branching primitives it's really cool
@aioia3885
Жыл бұрын
I recently got the Y combinator to work in my lambda calculus evaluator I might be wrong but I think that for it to work you can't use applicative order of evaluation but you also can't use normal order of evaluation. I think the trick is to always perform the leftmost reduction
@aioia3885
Жыл бұрын
correction: for an interpreter that correctly beta reduces lambda calculus terms you cannot use applicative order of evaluation but you can use normal order of evaluation if do you reductions at the head position until getting a head normal form. you can then proceeded to reduce the terms that are not in the head of an application see the wikipedia article for beta normal form for more details
Your videos on functional design patterns made me learn functional programming!
@AByteofCode
Жыл бұрын
I'm glad to hear that!
Something that I find somewhat amusing is that if your lambda calculus is embedded in a more featureful language, it's actually pretty easy to convert from the lambda calculus representation to the higher level representation. For example, true True False = True, false True False = False to convert to a typed boolean. Similarly, numbers can be gotten by just passing a +1 function and a base case of 0.
@asdfghyter
Жыл бұрын
I also appreciate the reverse, that the `foldr` (or corresponding for other types, like `if` for bools) function converts an ordinary list into the church encoding of a list. And then giving cons (:) and [] to the church list/foldr gives back the ordinary list again. So we have a simple isomorphism between the two encodings. This is actually used for the optimization of list-fusion in Haskell. All of the list operations are converted into the corresponding version on church-lists, i.e. by using `foldr` and applying (:) [], then the generated functions are inlined and simplified using the normal function optimizations. This means that sometimes when you first generate a list, then do some operations on it and finally consume the list, the whole list can be optimized away so you only have a tight loop in the end.
@angeldude101
Жыл бұрын
I actually wrote a small basic church encoding library in the Nix programming language, which provides a very succinct way to write untyped lambda calculus, and converting to and from the church encoding is about as short as the original definitions. nil = cons: nil: nil; cons = head: tail: cons: nil: cons head (tail cons nil); toChurch = lib.foldr cons nil; fromChurch = util.apply2 (h: t: [h] ++ t) [];
@asdfghyter
Жыл бұрын
@@angeldude101 Wait, why not just define toChurch as: toChurch = xs: cons: nil: lib.foldr cons nil xs Edit: I guess it's pretty similar to your definition, just that it moves the lambda inside the foldr instead of outside. Yours is also more direct from the definition of cons and nil for church lists.
@angeldude101
Жыл бұрын
@@asdfghyter Also -Pointless- *Point-free* style. Nix's dynamic typing and extremely short lambda syntax makes it somewhat satisfying to write church-encoded values, even if it supports them first-class anyways. (The language is actually intended for a package manager, though it's really more of a build system and dependency manager.)
I see two problems: 1. Lambda calulus by itself has no semantics - saying that lambda abstraction is a function gives semantics for it. But lambda calculus are only the set of well-founded words, nothing else, there is no semantics about it. 2. The way in which terms are reduced can be other than lazy, because Church-Rosser theorem says that no matter how we reduce, we'll end up with normal form if there is one.
2:15 yes that is always the first step
@garklein8089
Жыл бұрын
love your videos, never expected to see you here
@AByteofCode
Жыл бұрын
Interesting... (Also ooh, first verified comment, very nice :D)
Over the summer I tried to use Lambda Calc to make a very basic computer. While theoretically possible, simulating it with reduction is so slow that I had to stop. It took minutes to run even the most basic things!
@AByteofCode
Жыл бұрын
One interesting thing to do is write a lambda calc interpreter than extend it with features until you eventualy have an actual programming language!
I would like to get more insights about theoretical computer science topics such as these. There are lots of pure coding youtube creators. I think that you would be a great educator for theoretical cs!
After just coming across another video that dealt with lambda calculus, I'm trying to wrap my mind around something I don't fully understand yet. That said, your video took me a long way, and thank you so much for making such a great explanation!
@AByteofCode
Жыл бұрын
:D Good luck with your lambda journey! If you have any questions do not hesitate to ask
@PunmasterSTP
Жыл бұрын
@@AByteofCode Thank you, and that was lambdawfully kind of you to say!
i only understood that functions are turing complete what a fun time my teacher will have trying to read my fully functioning code!
@AByteofCode
Жыл бұрын
Hehe :)
Tutorials like these are what mankind needs to grow towards enlightenment & unification 😃!
SS: I like your funny words, magic man 💖
Very clear! Looking forward to the Y combinator. And for that video would it be a good idea to use color so that arguments, when present on the right hand side, are yellow, for instance, while the function they are being are applied to is blue? Keeping track of what, at anyone time, is function and what is argument can be difficult.
@AByteofCode
Жыл бұрын
not sure how i'd do that but you're right, im gonna absolutely spend some time thinking about how to color code functions and arguments for maximum understanding im gonna be spending the next week streamlining my process so i can try making a schedule after that, so a color guideline could be something i work on
@willd4686
Жыл бұрын
How you gonna do that when it's all functions?
@AByteofCode
Жыл бұрын
@@willd4686 yeah idk i thought about it but didn't find anything
this is the least you need for turing completeness: functions, variables, abstraction, numbers and -recursion- control flow (no goto) subtract x and y, and if that's negative or 0, goto z. and variables (yes goto)
Nice! I am fan of lambda calculus, but this is really good recap of this topic! Only small correction: parens aren't required to call fn-s, also, mentioning beta- and eta-reduction is worth it (Sorry for bad english)
@AByteofCode
Жыл бұрын
Good points, and thanks for the kind words! I hesitated mentioning those things, but found they weren't necessary for the core of the video. People are used to calling functions with brackets and its valid notation, so I didn't mention the other, also valid method.
@uwuzote
Жыл бұрын
@@AByteofCode yea, i understand, but i think it's more natural/idiomatic
@AByteofCode
Жыл бұрын
@@uwuzote I do prefer the way it looks, just I had to cut out a lot of fluff to keep the video short so I stuck to the essentials lol
Damn bud, you are really good at producing concise explanations of complex CompSci topics it's taken me years to grasp... 🤭
@AByteofCode
Жыл бұрын
Thanks for the kind words!
very good job, I'm not really even sure what i'm learning at this point, but i figure if i just keep acrewing knowledge the dots should connect... at some point... theoretically
maybe it's just me but it was very difficult to keep up without rewatching two or three times
@AByteofCode
Жыл бұрын
Definitively not just you lol. I try to fit too much into not enough time which makes things hard to grasp. I'm still trying to figure out the right rhythm!
Wikipedia describes lambda calculus as "...a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution." This video makes that clear.
In a sense, this is trivial, in another it is pure genius .
I like the succ function
I learned this by one of the ocaml writers. Ascander Suárez was my languages teacher.
I wish Mathematicians used lambdas, currying, and partial applications more often, and were more familiar with type theory and proof assisting compilers such as Coq, Agda, and Lean4. Perhaps if highschools offered 4 years of programming in the same way schools offered four years of math, we could see more Mathematicians lean towards constructivism.
How did you pack so much info into 4 minutes? Amazing
@AByteofCode
Жыл бұрын
The secret is making it go so fast most people don't actually understand anything :)
I want this to become a tutorial on FP ! Also, why church/ turing instead of Church/ Turing ?
@AByteofCode
Жыл бұрын
I don't know about the capitalization thing. Otherwise, I think after the Y Combinator video I'm gonna take a break from functional programming to make videos on stuff I'm a bit more familiar with, but if I were to do a FP tutorial, what would you want in it?
babe wake up new byte of code video
@AByteofCode
Жыл бұрын
:)
I have ADHD so these short format videos are quite tasty
The Church encoding of lists (almost of the same as for numbers, but the function takes an extra element, corresponding to a single element in the list) is actually used for performance optimization in Haskell. The optimization is called list-fusion. All of the list operations are converted into the corresponding version on church-lists, by using `foldr` to turn a Haskell list to a Church-list and applying (:) [] to convert a Church-list to a Haskell-list, then the generated functions are inlined and simplified using the normal function optimizations. And any redundant cases of converting in one direction just to immediately convert it back are eliminated. This means that sometimes when you first generate a list, then do some operations on it and finally consume the list, the whole list can be optimized away so you only have a tight loop in the end. One cool thing about this optimization is that it is implemented completely in library-code. Nothing is built into compiler itself. The library code just tells the compiler “when you see this pattern, replace it with that pattern” and the rest falls out automatically.
@asdfghyter
Жыл бұрын
More concretely, we have: -- A list of `a`s is either an empty list or a single `a` followed by a list data List a = [] | a : List a -- This is the elimination rule for list and also converts a list to a church list -- > foldr f z [1,2,3] -- f 1 (f 2 (f 3 z)) foldr :: (a -> b -> b) -> b -> List a -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) -- This function converts back from a chruch numeral to a list build :: (forall b. (a -> b -> b) -> b -> b) -> List a build curchList = churchList (:) [] -- These two form an isomorphism, so -- foldr (:) [] xs = xs -- and -- foldr f z (build g) = g f z -- We tell the compiler to use the above simplification like this: {-# REWRITE “foldr/build” forall f z g. foldr f z (build g) = g f z #-} -- finally we can implement a function using this map :: (a -> b) -> List a -> List b map f as = build (\ cons nil -> foldr (\a bs -> cons (f a) bs) nil as) {- -- corresponds to this: map f [] = [] map f (a:as) = f a : map f as -} And now finally, if we were to call map twice, the two uses would automatically fuse together: map f (map g list) = build (\ cons nil -> foldr (\a bs -> cons (f a) bs) nil (build (\ cons' nil' -> foldr (\a' bs' -> cons' (g a') bs') nil' list) )) -- use the foldr/build rule = build (\ cons nil -> foldr (\a' bs' -> (\a bs -> cons (f a) bs) (g a') bs') nil list) = build (\ cons nil -> foldr (\a' bs' -> cons (f (g a')) bs') nil list) = map (\x -> f (g x)) list which is exactly the simplification we wanted
Respect!
Now you know what I am going to create my next Javascript framework in!
@AByteofCode
Жыл бұрын
o.o What horrors will come of this? Then again, I did have the idea of making a framework where instead of writing javascript you write html tags which define program logic and stuff :) Hello World
@wlockuz4467
Жыл бұрын
@@AByteofCode So basically React? 🤣
@AByteofCode
Жыл бұрын
@@wlockuz4467 from what i know in react you write html inside your javascript, im more thinking you write javascript as html
@wlockuz4467
Жыл бұрын
@@AByteofCode oh so you mean plain html tags that can somehow express logic? That sounds disgusting, I would love to see it.
@AByteofCode
Жыл бұрын
@@wlockuz4467 :) I'd wanna try a new format of showcasing horrible things I make so I'll definitively be doing that video someday
Omg well done dude
Awesome video, but very fast paced, it's hard to comprehend without pausing and unpausing constantly
@AByteofCode
Жыл бұрын
Very sorry about that. I'll try doing better in the future!
awesome
Sometimes existiance feels like lambda calculus and we are adaptive functions because we change with every experience. Maths and the nature of the universe is complicated.
I don't take collage and don't understand calculus, but your content so interesting it make me want to go to collage
@nekroxxigasmith1093
Жыл бұрын
Just so you know, this video has nothing to do with "math" or university calculus, only the name is similar
@gneryze
Жыл бұрын
@@nekroxxigasmith1093 oh it do
And that's why we use imperative languages
Great video! How much time does it take you to edit?
@AByteofCode
Жыл бұрын
Each video takes about 40 hours to make including all the research and stuff :|
@kellersefi
Жыл бұрын
@@AByteofCode that's a lot! There are tools that automate parts of the editing process. Maybe they can save you some time.
@AByteofCode
Жыл бұрын
@@kellersefi I'm constantly thinking about ways to make the process more efficient. I've noticed that the more practical a video is, the less time it takes to make, so I might try to lean in that direction. Also shorter videos perform a lot better, and are easier to make, so that's another method of optimization. Other than those two, there isn't a lot of time saving I could do before starting to outsource some of the work
"If you don't understand it, don't worry, it will make sense relatively soon" X 9 "then end"
@AByteofCode
Жыл бұрын
by soon i meant about 3 weeks lmao
the hardest part is that its turtles all the way down
Whenever people on the internet make me feel smart in comparison, I try figuring out functional programming again. That usually lowers me back to baseline.
@AByteofCode
Жыл бұрын
Dunning krueger effect bypass :)
@LambdaJack
Жыл бұрын
Because proper explanation wouldn't be "functional" and even less "lambda". It means you are thinking. It is like studying division through Roman Numerals. What a wonderful theory and exposition would it be.
I like the video and it's great to have such a fast-running & dense video, but it is annoying to want to soak-in the visuals, but need to constantly be back-skipping. Maybe have an extended video where you just re-use the same stuff, but just slow down. Essentially, this would be the "TL:DT" (too long, didn't think) version, and the other would be if you want to soak-in the visuals. But if I had to choose one vs the other, i'd go with this one, as the video could just be replayed a few times. I don't think that's the ideal though for how humans internalize; pacing has value.
@AByteofCode
Жыл бұрын
I agree, this video was too fast. I think when you spend an hour on 15 seconds of content, and when you can't get live previews (i had a much worse pc when i made that video), you really don't notice the pace. That's the main thing I need to work on for future content, and I'll probably revisit these couple of videos to make them more accurate and understandable!
is the description here correct? looks like some wip stuff is left over :) good vid tho
@AByteofCode
Жыл бұрын
lmao forgot to remove that, thanks for pointing it out!
@eldattackkrossa9886
Жыл бұрын
@@AByteofCode gotcha 😎
Can you actually explain what 0:41 actually means? As an example, let's say f(x) = 2x. If I have pseudo-code that looks like _a = 5_ _f(5)_ Now when I do _return a_ I should get 10. If I converted it to your format I have λa.(f(a))(5) Now, what does this actually mean?? I understood when you said that λinput.output is equivalent to function(input) { return output } so when I try to change λa.(f(a))(5) into this format I get function(a) { return (f(a))(5) } And I still don't understand what (f(a))(5) means.
@garklein8089
Жыл бұрын
when you convert it to his format, you get (λa.(f(a)))(5) (note the grouping) then, converting it to js-like, you get (function (a) { return f(a) })(5) you can see that in that function, `a` is bound to 5 despite us never using any variables
The way variables are defined made me realize that global vars are impossible in this lang! I see this as an absolute win, lol. In addition (pun indented (pun intended too (there's a typo, read twice (I think I have too many parentheses, this looks like Common Lisp)))), vars are only available within the strict scope in which they were defined, forcing vars to always be private and local, and encouraging devs to pop the vars from the stack ASAP, thereby reducing memory usage as a side-affect (pun intended too)
@AByteofCode
Жыл бұрын
Two many puns in that comment :)
And also, it's all about this: en.wikipedia.org/wiki/SKI_combinator_calculus
basic, but clean! neat :)
Beauty 🙂
Oh my
Me: Wait, it was just LISP ? (): (always has been)
In summary, functions are little pieces categorized as turing complete, aka, made in hell
I am watching this at 01:27am and didn’t program for more than 12 years
Can we talk talk about why something called the "succ()" function exists 😂
Inline functions are also nice
@AByteofCode
9 ай бұрын
In python, inline functions are made with the "lambda" keyword so i'd argue they're mostly the same (except inlines are more practical since you can have other stuff in it)
Interesting video, but honestly if this is meant to actually teach something (more than just the binary knowledge "yes, it's theoretically possible to do this"), how about showing some real code executed etc.? Is there a language which supports this kind of chained lambdas?
@AByteofCode
Жыл бұрын
Uh haskell technically has lambda expressions, and python has a "lambda" keyword but both of these work a bit differently to what this video explained. Ultimately, while there are some interpreters for lambda calculus, its still calculus and programming in this is about as worth doing as using brainf*ck: its fun but not useful :)
@MiTheMer
Жыл бұрын
@@AByteofCode Okay, that makes sense. Am mostly watching programming vids so I came to this video with a wrong mindset :)
Sure, it's also a way to write something that ensures you are the only one who can ever understand what that thing does. Or maybe not even you.
@AByteofCode
Ай бұрын
Think of it as the extreme sports of programming. It’s an interesting challenge but definitely not meant for production (I mean division has a complexity of n^6 if I remember correctly)
@Leonhart_93
Ай бұрын
@@AByteofCode Yeah. I have however seen many serious proponents for purely functional programming, with extremely no-chill restrictions and all, and I must say I have no idea how they are going to integrate that in a team. I imagine people like it because it makes them feel smart, but I would rather not make separate functions to avoid a + b or complicated recursion nesting to avoid a simple loop 😂
@AByteofCode
Ай бұрын
@@Leonhart_93 I find that my imperative code has been less buggy since I learnt some functional principles. Keeping an eye on side effects for example, is a pretty good idea. IMO, write code with a mix of both, as they both have some solid advantages and aren't completely incompatible
@Leonhart_93
Ай бұрын
@@AByteofCode Sure, some principles are nice to understand, like trying to use more pure functions instead of having too many side effects. BUT, I will never get to the point of chaining 5 functions together just so that I avoid doing "if (x % 2) a += b; " 😂
Wait, it's all relations?
Would be interested in a video on how horn clauses are turing complete.
@AByteofCode
Жыл бұрын
added that to my "stuff to research" list :)
thecangculus
It succs🤣
@AByteofCode
Жыл бұрын
Just like the zucc
tf is \b.b(false)(true) supposed to mean?
@AByteofCode
10 ай бұрын
In JS that would make "bool => bool(valueiffalse, valueiftrue)" So if instead of bool being a function but was an actual boolean, it'd be, in python "valueiftrue if bool else valueiffalse"
noparency data fites
wizonly future
@user-pr6ed3ri2k
Жыл бұрын
😰😨
oragate
started taking functional programming classes two weeks ago, worst idea ever
@AByteofCode
9 ай бұрын
Once you get the hang of it, you'll at least sound smart
Is this #some2 ?
@AByteofCode
Жыл бұрын
Some2 ended a few weeks before i uploaded this, which is a shame because this video would have fit as a some2 submission
and4
loadinginup
haskell
Now do SKI calculus
@AByteofCode
Жыл бұрын
Someday lol, but don't worry its on my mind :)
@ccgarciab
Жыл бұрын
@@AByteofCode wooh, didn't expect that you'd actually do it, but I'm happy
turn(i(ing?)?) value booea
binarian
I understood nothing and I had fun
@AByteofCode
Жыл бұрын
So I give off the same experience as school :)
Your multiplication and exponentiation operators are needlessly complex. If done right, they are simpler than addition. For example, exponentiation is just reverse function application!
@AByteofCode
Жыл бұрын
"reverse function application" please elaborate also yeah my resident lambda expert told me about the simpler methods but the one showed was the most intuitive and so best choice for a quick intro :)
@siquod
Жыл бұрын
@@AByteofCodeWell, if (f x) denotes the function f applied to the argument x, and if b and n are Church numerals, then (n b) is the Church numeral for bⁿ. I agree that it is not immediately obvious why this is so. It's a fun exercise to wrap your head around it. What's easier to understand is that the product of two Church numerals m and n is (λs → (m (n s))). To understand this, it helps to think about Church numerals as accepting a "stepper function" and a "starting value". The numeral c first converts the stepper function argument into its n-fold iterate and then applies it to the starting value. That's the same as applying it c times in a row to the starting value, but we don't need to know the starting value in order to form the c-fold iterate of the stepper function. If s is a stepper function (e.g. (λv → (v + 1)), but could be anything), and we feed it to the Church numeral n, we get back its n-fold iterate (In the example, this would be (λv → (v + n)). This has also the same type of a stepping function as s, so if we feed it to m, we get the m-fold iterate of the n-fold iterate of s, which is the m×n-fold iterate of s. This definition of multiplication is more concise, because it doesn't even mention the starting values, but operates on the stepper functions. It is slightly more abstract because it uses the concept of higher order functions and never goes down to the level of "concrete values", but IMO this abstraction pays of because in lambda calculus, there are no "concrete values", it's functions all the way down and this way to define multiplication does it justice.
thanks for this video, now i know that i never want to study lambda calculus :)
Just write a lambda calculus interpreter.
well ``` int x() { return 5 } ```
I don't know who i am... I don't know why i'm here All i know is a monad is a monoid in the category of endofunctors
... What?
jesus, this looks like hell
nouhdup timez ack 1
@user-pr6ed3ri2k
Жыл бұрын
beturn
What the hell just happened? Very good explanation, but i don't have a clue what you're talking about fella, not a damn clue i tell you. Do you have any soup? 🙏
@AByteofCode
7 ай бұрын
I have some onion soup if you want
🙀
Wat
Thats kind of misleading imo. Because you go beyond what functions do. Specifically you define one. But doesnt it mean that syntaxis is turing complete and not the functions?
@stasglazkov8734
Жыл бұрын
Its like there is something you can only do at home and the statement goes: In order to do A you need to go home first. Then you go home independently of doing A. Make sure you stay within the contains of home by not leaving it and make a video YOU NEVER NEED TO GO HOME TO DO A EVER AGAIN presenting your case where you are at home and have everything you need AND work with select few things that inherently dont require you leaving your home. Its defining the function that is turing complete and not the function. For that matter you could define anything and make it do computations. Just depending on your selection you get some things for free and some by workarounds. Try doing the same in the universe of Plato where you have mathematical ideals of functions. You will quickly realise how functions dont do shit on their own and its basically you mind that expands their capacities to turing completeness.
its a function, ok great it can do most of the things, but I failed to understand how it is" turing complete" was it all just clickbait?
@AByteofCode
Жыл бұрын
Generally, a turing complete system is capable of conditional looping and logic. While I didn't specifically prove TCness, its really hard to do that so we just stick to the signs, which is the interesting stuff. I do get where you're coming from and I'm gonna try and find ways to incorporate proofs of TCness in future videos of the format "why ... is TC"
f
Λ λ
i did not understand a single thing here.
Oh man I hate lambda calculus with my soul, what a twisted idea
sordof moudup time wide times
@user-pr6ed3ri2k
Жыл бұрын
chewing completeness
@user-pr6ed3ri2k
Жыл бұрын
waild loops insenetOvfA function Y ombinator might here
@user-pr6ed3ri2k
Жыл бұрын
selatsa
@AByteofCode
Жыл бұрын
are you ok lol
it's way too fast goddamn
great thumbnail
@AByteofCode
Ай бұрын
Thank you!!