On the likelihood of normalization in combinatory logic

DOI10.1093/LOGCOM/EXX005zbMATH Open1454.03022arXiv1607.04908OpenAlexW2592901442MaRDI QIDQ3133193FDOQ3133193

Authors: Maciej Bendkowski, Marek Zaionc, Katarzyna Grygiel 

Publication date: 13 February 2018

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

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{\%}$.

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

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

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40)

Cited In (9)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the enumeration of closures and environments with an application to random generation
• Title not available (Why is that?)
• Asymptotic properties of combinatory logic
• Title not available (Why is that?)
• 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)