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 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.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00372035
Author David, René, Grygiel, Katarzyna, Kozic, Jakub, Raffalli, Christophe, Theyssier, Guillaume, Zaionc, Marek
Maintainer CCSD
Last Updated October 30, 2026, 15:06 (UTC)
Created October 30, 2026, 15:06 (UTC)
Identifier hal-00372035
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire de Mathématiques (LAMA) ; Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)
creator David, René
date 2012-05-01T00:00:00
harvest_object_id 00f04d38-5935-4c3f-baa7-b10f314658ea
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-09-27T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/0903.5505
set_spec type:UNDEFINED