René David

  1. Some properties of random lambda terms.

    Authors: René David, Christophe Raffalli, Guillaume Theyssier, Katarzyna Grygiel, Jakub Kozic, Marek Zaionc
    Subjects: Logic
    Abstract

    We present quantitative analysis of various (syntactic and behavioral)
    properties of random lambda-terms. Our main results are that asymptotically all
    the terms are strongly normalizing and that any fixed closed term almost never
    appears in a random term. Surprisingly, in combinatory logic (the translation
    of the lambda-calculus into combinators) the result is exactly opposite. We
    show that almost all terms are not strongly normalizing. This due to the fact
    that any fixed combinator almost always appears in a random combinator.

Syndicate content