[HN Gopher] Fixed-point combinator
       ___________________________________________________________________
        
       Fixed-point combinator
        
       Author : tosh
       Score  : 38 points
       Date   : 2024-02-23 15:26 UTC (7 hours ago)
        
 (HTM) web link (en.wikipedia.org)
 (TXT) w3m dump (en.wikipedia.org)
        
       | konstantinua00 wrote:
       | I don't get it
       | 
       | example shows that it's y(g)->g(y(g)), not the opposite...
        
         | toxik wrote:
         | No, it shows that `Y g = g (Y g)`, so both ways.
        
           | ted_dunning wrote:
           | To clarify for people who are sloppy readers like me, the
           | important difference here is the difference between `=` and
           | `=>`, not the difference in notation between `Y(g)` and `Y
           | g`.
        
         | youzicha wrote:
         | Indeed. I think this something that people are often confused
         | about, e.g. one blogger[0] comments:
         | 
         | > The key to understanding the fixpoint theorem, for me anyway,
         | was realizing that when it says FG=G, it does _not_ mean that
         | for every F there is a G such that by calling F with parameter
         | G one can get back G. I mention this in the blog post, above.
         | The equality operator in FG=G is the equivalence relation
         | induced by the calculus rewriting relation: that is, it 's the
         | _symmetric_ reflexive transitive closure of the rewriting step
         | relation. When you look at the proof of the theorem, it
         | actually works by constructing an expression G such that
         | evaluating G produces, as an intermediate result, FG. There is
         | no need for F to even be a function, and if F is a function it
         | doesn 't matter what, if anything, F would actually do when
         | called, because the proof of the theorem doesn't involve
         | calling F.
         | 
         | I think the name "fixpoint combinator" is kindof bad, it it was
         | called e.g. the "recursion combinator" I think people would
         | find it more intuitive.
         | 
         | [0] https://fexpr.blogspot.com/2013/07/bypassing-no-go-
         | theorems....
        
           | genezeta wrote:
           | The name, fixed point, is a more generic or general concept
           | in mathematics.
           | 
           | Given a function _f_ , we say that an element _c_ in the
           | domain of _f_ is a fixed point for _f_ if it satisfies that
           | _f(c) = c_. In a different nomenclature, if you consider _f_
           | a  "transformation", then _c_ satisfies that it  "remains
           | fixed through the transformation".
           | 
           | The fixed-point combinator is called so, because it "produces
           | fixed-points for a function". That is, given a function _f_ ,
           | then _FPC(f)_ is a fixed-point for _f_. So, if we call _c =
           | FPC(f)_ , then _f(c) = c_. Or, more classically _f(FPC(f)) =
           | FPC(f)_ or _f(Y(f)) = Y(f)_.
           | 
           | ---
           | 
           | Note that when talking about fixed points in general, the
           | domain of the _f_ function is whatever -but usually you may
           | have studied it with numbers-. But when talking about the
           | fixed-point combinator the domain is functions themselves.
        
       | tromp wrote:
       | Curiously, Freek Wiedijk implemented a fixed point combinator in
       | pure portable C99 in his 2014 IOCCC entry [1] that computes 10
       | factorial with no loops, as explained in [2].
       | 
       | [1] https://www.ioccc.org/2014/wiedijk/prog.c
       | 
       | [2] https://www.ioccc.org/2014/wiedijk/hint.html
        
       ___________________________________________________________________
       (page generated 2024-02-23 23:01 UTC)