ASYMPTOTICALLY ALMOST ALL lambda-TERMS ARE STRONGLY NORMALIZING

作者：David Rene^*; Grygiel Katarzyna; Kozik Jakub; Raffalli Christophe; Theyssier Guillaume; Zaionc Marek

来源：Logical Methods in Computer Science, 2013, 9(1): 02.

DOI：10.2168/LMCS-9(1:02)2013

• lambda-calculus
• combinatorics
• normalisation
• combinatory logic

We present a quantitative analysis of various (syntactic and behavioral) properties of random lambda-terms. Our main results show that asymptotically, almost all 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 is due to the fact that any fixed combinator almost always appears in a random combinator.

• 出版日期2013