Let’s verify that it behaves like rec by giving it an input g: Y g = λf.(λx.f (x x)) (λx.f (x x)) g (replace Y with its definition) Like loop, we can encode rec in lambda calculus too! But we call rec ‘Y’ in lambda calculus this time, because this encoding is the famous Y-combinator that lets you have recursion in any languages: Y = λf.(λx.f (x x))(λx.f (x x)) The general recursion function can easily become any recursive function because f can be whatever you like! The Y-combinator = f (f (f (.)).) (infinite replacements can be made) = f (f (rec f)) (replace rec f with f (rec f)) In mathematics, it looks like this: rec f = f (rec f) A general recursion function (named rec) takes itself as the input. Self-application takes us to general recursion. (λx.x x) is applied to an input like itself! General Recursion We got this property from the self-application of the function (λx.x x). You can see that encoding loop as above gives us a function that behaves like loop. = (λx.x x)(λx.x x) (infinite replacements can be made)
In loop, one applies the function (λx.x x) to the input (λx.x x): (λx.x x)(λx.x x) = (λx.x x)(λx.x x) (replace each x with the input) Recall that in lambda calculus, what we do with two items side by side is to apply the first item as a function to the second item as an input. When you evaluate loop, you go to loop‘s definition, which is loop! We can encode a function that behaves like loop in lambda calculus: loop = (λx.x x)(λx.x x) The function loop does only one thing: calling itself.
In this video, Professor Hutton shows us the simplest recursion he can think of: If you haven’t read my last post already, please do so! It’d be easier for you to follow this post, especially if you don’t know any lambda calculus. This enables you to do recursion in any languages! In this post I further proves the point by encoding recursion in it. In the last post I talked about how powerful lambda calculus is.
0 kommentar(er)
