Quantitative aspects of normal-order reduction in combinatory logic

We present a quantitative basis-independent analysis of combinatory
logic. Using a general argument regarding plane binary trees with
labelled leaves, we generalise the results of David et al. and
Bendkowski et al. to all Turing-complete combinator bases proving,
inter alia, that asymptotically almost no combinator is strongly
normalising nor typeable. We exploit the structure of recently
discovered normal-order reduction grammars showing that for each
positive n, the set of SK-combinators reducing in n normal-order
reduction steps has positive asymptotic density in the set of all
combinators. Our approach is constructive, allowing us to
systematically find new asymptotically significant fractions of
normalising combinators. We show that the density of normalising
combinators cannot be less than 34%, improving the previously best
lower bound of approximately 3%. Finally, we present some
super-computer experimental results, conjecturing that the density of
normalising combinators is close to 85%.