[Haskell-beginners] Re: fixpoint operator for ULC with specific reduction property

Heinrich Apfelmus apfelmus at quantentunnel.de
Thu Nov 4 07:23:16 EDT 2010

ben wrote:
> I'm looking for a fixpoint operator Z for the untyped lambda calculus
> that has the property
> Z g --> g (Z g)
> for any g.
> The best-known fixpoint operator Y := \f. (\x. f (x x)) (\x. f (x x))
> does not have this property, but only
> Y g --> T <-- g (Y g)
> for some T.
> Does anybody know such a Z I'm looking for?

I think the Turing fixed point combinator does exactly that. It's defined as

    Theta = (λxf.f(xxf))(λxf.f(xxf))



Heinrich Apfelmus


More information about the Beginners mailing list