On the likelihood of normalization in combinatory logic

DOI10.1093/LOGCOM/EXX005MaRDI QIDQ3133193zbMATH OpenOpenAlexFDO

Authors Maciej Bendkowski, Marek Zaionc, Katarzyna Grygiel

Publication date 13 February 2018

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.04908

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40)

Abstract: 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 $mathbfSmathbfK$-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\mathrm{\%}$, improving the previously best lower bound of approximately $3\mathrm{\%}$. Finally, we present some super-computer experimental results, conjecturing that the density of normalising combinators is close to $85\mathrm{\%}$.

Recommendations

• Asymptotic properties of combinatory logic
• Asymptotically almost all \lambda-terms are strongly normalizing
• Normal forms in combinatory logic
• Normal-order reduction grammars
• Combinatorics of \(\lambda\)-terms: a natural approach

Cited in

(9)

• scientific article; zbMATH DE number 7559273 (Why is no real title available?)
• scientific article; zbMATH DE number 4199606 (Why is no real title available?)
• On the enumeration of closures and environments with an application to random generation
• scientific article; zbMATH DE number 7029315 (Why is no real title available?)
• Asymptotic properties of combinatory logic
• scientific article; zbMATH DE number 598799 (Why is no real title available?)
• Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels
• Counting environments and closures
• The combinator M and the Mockingbird lattice

This page was built for publication: On the likelihood of normalization in combinatory logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133193)