Y, Turing and U

turing.hs

-- having 
u x = x x                                                  -- the same piece of paper, or
v g x = x (g g x)    -- !!  v v x == x (v v x)  !! --      --   a new piece of paper with 
                                                           --     the same text on it ...
-- reduce 
u u = u u = u u = ...

u v = v v = \x-> x (v v x)
u v x = v v x = x (v v x) == x (x (v v x)) == x (x (x (v v x))) == ...
                          == x (u v x)

-- turns out, it's a Turing FixPoint Combinator: Theta = uv; Theta x = uvx = vvx = x(vvx)
-- https://en.wikipedia.org/wiki/Fixed-point_combinator#Other_fixed-point_combinators

Y f = U (\x-> f (x x)) = (\x-> f (x x)) (\x-> f (x x)) = f ( (\x-> f (x x)) (\x-> f (x x)))
H f x = f (x x)   -- OlegK calls H _U_, and U he calls _Delta_, @
                  -- http://okmij.org/ftp/Computation/fixed-point-combinators.html#Self-application
                  -- also http://plato.stanford.edu/entries/type-theory/ calls U _Delta_
Y f = U (H f) = H f (H f) = f (H f (H f))    ........ Y == U.H == BUH  !!   also,  Y == SHH !!

fact n = 1 if n<2 else n_fact (n-1)
nrfact g n = 1 if n<2 else n_g g (n-1)
fact = nrfact g = g g

Prelude> :t let _Y = foldr id undefined . repeat in _Y
let _Y = foldr id undefined . repeat in _Y :: (b -> b) -> b