Fixed-point Combinator - Existence of Fixed-point Combinators

Existence of Fixed-point Combinators

In certain mathematical formalizations of computation, such as the untyped lambda calculus and combinatory logic, every expression can be considered a higher-order function. In these formalizations, the existence of a fixed-point combinator means that every function has at least one fixed point; a function may have more than one distinct fixed point.

In some other systems, for example in the simply typed lambda calculus, a well-typed fixed-point combinator cannot be written. In those systems any support for recursion must be explicitly added to the language. In still others, such as the simply typed lambda calculus extended with recursive types, fixed-point operators can be written, but the type of a "useful" fixed-point operator (one whose application always returns) may be restricted. In polymorphic lambda calculus (System F) a polymorphic fixed-point combinator has type ∀a.(a→a)→a, where a is a type variable.

Read more about this topic:  Fixed-point Combinator

Famous quotes containing the words existence of and/or existence:

    This seems to be advanced as the surest basis for our belief in the existence of gods, that there is no race so uncivilized, no one in the world so barbarous that his mind has no inkling of a belief in gods.
    Marcus Tullius Cicero (106–43 B.C.)

    Some say existence like a Pirouot
    And Pirouette, forever in one place,
    Stands still and dances, but it runs away;
    It seriously, sadly, runs away
    To fill the abyss’s void with emptiness.
    Robert Frost (1874–1963)