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.

[@pointthink]

Ow my brain

[@aydynx]

really simple to understand if you have some background on cpu architecture and logic gates

[@w花b]

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?

[@orterves]

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

[@Truttle1]

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

[@alexander191297]

This video: Explains lambda calculus. What my brain gets: *S U C C*

[@AByteofCode]

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

[@markosth09]

I like to call λ calculus an unintentional esolang

[@AByteofCode]

I totally agree lol

[@dgcp354]

I never fully understand your video but still, it's short and I like it.

[@user-zu1ix3yq2w]

Boolean algebra

[@LyricWulf]

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)

[@olillin]

Loving the new mic quality, and your content is both educational and entertaining. Keep it up!

[@AByteofCode]

Thanks man! Shall do :)

[@japper12321]

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.

[@marcolerena456]

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!

[@ruuku2743]

Your videos on functional design patterns made me learn functional programming!

[@AByteofCode]

I'm glad to hear that!

[@zyansheep]

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

[@remiwi2399]

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!

[@qedqubit]

Tutorials like these are what mankind needs to grow towards enlightenment & unification 😃!

[@selfspectrum9369]

SS: I like your funny words, magic man 💖

[@angeldude101]

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

[@Userjdanon]

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!

[@kvolikkorozkov]

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 :)

[@PunmasterSTP]

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!

[@otterlyso]

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

[@mr.duckie._.]

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)

[@WolvericCatkin]

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!

[@legoenforcer7734]

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

[@uwuzote]

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

[@anywallsocket]

In a sense, this is trivial, in another it is pure genius .

[@trp]

I like the succ function

[@blueguy5588]

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.

[@Xayuap]

I learned this by one of the ocaml writers. Ascander Suárez was my languages teacher.

[@nuclearcatapult]

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.

[@MetaMaths]

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?

[@wlockuz4467]

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

[@Zmunk19]

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!

[@paxdriver]

Omg well done dude

[@dragolov]

Respect!

[@diedoktor]

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 :)

[@RedStone576]

awesome

[@Simonheart13]

babe wake up new byte of code video

[@AByteofCode]

:)

[@xyzphyr]

I have ADHD so these short format videos are quite tasty

[@asdfghyter]

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

[@otesunki]

the hardest part is that its turtles all the way down

[@timmydirtyrat6015]

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!

[@MrRedstonefreedom]

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!

[@kellersefi]

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

[@gm2407]

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.

[@gneryze]

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

[@ryuk5709]

And that's why we use imperative languages

[@howareyou4400]

"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

[@xXJ4FARGAMERXx]

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

[@eldattackkrossa9886]

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 😎

[@federicoagustinsawadyoconn2716]

And also, it's all about this: en.wikipedia.org/wiki/SKI_combinator_calculus

[@AdrX003]

Oh my

[@sempersolus5511]

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.

[@Rudxain]

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 :)

[@principleshipcoleoid8095]

Inline functions are also nice

[@AByteofCode]

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)

[@rpxdytx]

In summary, functions are little pieces categorized as turing complete, aka, made in hell

[@im-essi]

basic, but clean! neat :)

[@saroamirkhanyan]

Beauty 🙂

[@MiTheMer]

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 :)

[@insertoyouroemail]

Wait, it's all relations?

[@electroflame6188]

Would be interested in a video on how horn clauses are turing complete.

[@AByteofCode]

added that to my "stuff to research" list :)

[@azeton128]

I am watching this at 01:27am and didn’t program for more than 12 years

[@Maartz]

Me: Wait, it was just LISP ? (): (always has been)

[@rusluck6620]

tf is \b.b(false)(true) supposed to mean?

[@AByteofCode]

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"

[@Leonhart_93]

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; " 😂

[@user-pr6ed3ri2k]

and4

[@user-pr6ed3ri2k]

thecangculus

[@alejrandom6592]

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

[@user-pr6ed3ri2k]

loadinginup

[@user-pr6ed3ri2k]

wizonly future

[@user-pr6ed3ri2k]

😰😨

[@ianmccubbin7575]

Can we talk talk about why something called the "succ()" function exists 😂

[@user-pr6ed3ri2k]

oragate

[@user-pr6ed3ri2k]

turn(i(ing?)?) value booea

[@user-pr6ed3ri2k]

noparency data fites

[@widepootis]

started taking functional programming classes two weeks ago, worst idea ever

[@AByteofCode]

Once you get the hang of it, you'll at least sound smart

[@ccgarciab]

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

[@codexed-i]

Just write a lambda calculus interpreter.

[@shaileshaanand]

It succs🤣

[@AByteofCode]

Just like the zucc

[@TheMightyShell]

I understood nothing and I had fun

[@AByteofCode]

So I give off the same experience as school :)

[@heliusuniverse7460]

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

[@siquod]

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.

[@leptosurreal460]

... What?

[@funmath3835]

haskell

[@krawieck]

thanks for this video, now i know that i never want to study lambda calculus :)

[@user-pr6ed3ri2k]

binarian

[@SuperchargedCow]

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]

I have some onion soup if you want

[@TuMadre8000]

jesus, this looks like hell

[@rusluck6620]

well ``` int x() { return 5 } ```

[@maxron6514]

Wat

[@Waferdicing]

🙀

[@user-pr6ed3ri2k]

nouhdup timez ack 1

[@user-pr6ed3ri2k]

beturn

[@planktonfun1]

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"

[@stasglazkov8734]

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.

[@vikingthedude]

f

[@Templarfreak]

i did not understand a single thing here.

[@fromant65]

Oh man I hate lambda calculus with my soul, what a twisted idea

[@Lucas_strable]

Λ λ

[@user-pr6ed3ri2k]

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

[@MeanSoybean]

it's way too fast goddamn

[@klembokable]

great thumbnail

[@AByteofCode]

Thank you!!