Asymptotically almost all \lambda-terms are strongly normalizing
Asymptotically almost all \lambda-terms are strongly normalizing
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 …