4 ms·
This is absolutely fascinating, but I'm having trouble really grokking the principle behind this. I understand fixed points of mathematical functions with numbe
by jpadvo 15y ago
This is absolutely fascinating, but I'm having trouble really grokking the principle behind this. I understand fixed points of mathematical functions with numbers, but my mind seems to explode in the transition to functions of functions.
Is there a really clear explanation anywhere of the idea behind all this? Or is it the kind of thing where this is simple as it gets, and I just need to put in more work to get it?
- qntm 15y agoI'm going to write up some sort of explanation once I can get my head around it myself.
- dilap 15y agoI don't know if these ramblings will help, but here are some thoughts :) First of all, the Y-combinator is a function of a function of a function (of a number), so we're three levels deep, which is part of what causes the head-spinning, I think. So ignore the Y-combinator for the moment. Simply consider the function of a function (of a number) F: F = function (f) { return function(n) { return (n == 0) ? 1 : (n*f(n - 1)); }; }; Here the argument f is a function number -> number, and the return value from F is itself also a function number -> number. We can pass whatever functions from numbers to numbers we want to F to make new functions from numbers to numbers. E.g., we could pass in exf1 = function(n) { return n }; and we'd have F(exf1) = function(n) { return (n == 0) ? 1 : (n*(n - 1)) }; Or we could pass in something like exf2 = function(n) { return 1; } in which case we'd get F(exf2) = function(n) { (n == 0) 1 : n - 1 }; So now imagine god gives us the factorial function: fact: number -> number fact(n) = n*(n - 1)*...*1 Then if we pass this in to F we get F(fact) = function(n) { return n == 0 ? 1 : n*fact(n - 1) } But the above is simply a recursive definition of fact! So F(fact) = fact, i.e., fact is a fixed point of F. Now consider the Y combinator. We know the Y combinator gives us a fixed point of a functional, i.e., F(Y(F)) = Y(F) (Note Y(F) is simply a function, even though the argument to Y is a functional, i.e., Y: functional -> function or Y: (function -> function) -> function or Y: ((number -> number) -> (number -> number)) -> (number -> number)) So we know that one possible value for Y(F) is fact. The article makes the claim that there is only one fixed point of F, which means Y(f) must actually be fact, but to be honest, I'm not sure why we know there can't be other fixed points of F which Y(F) might give us (though maybe this is obvious and I'm being stupid :). But anyway we can tell by tracing through the definition of Y that it we really do get Y(F) = fact.
- dilap 15y agoOh, in the morning it occurs to me that a simple argument by induction will show that any function g with g = F(g) must in fact be factorial, so that's one way we can know the fixed point is unique. :)
- jpadvo 15y agoThanks, dilap! That does make the concept a lot clearer. Especially the Haskell-ish typing. :)
- qntm 15y agoThe best I've managed is this: http://qntm.org/fib http://qntm.org/fib I find that removing all mention of Y combinators made the whole thing a lot easier to read.
- jpadvo 15y agoThank you! That was very helpful. :)