View in EDS PDF Full Text

On the likelihood of normalization in combinatory logic.

Saved in:
Bibliographic Details
Title: On the likelihood of normalization in combinatory logic.
Authors: BENDKOWSKI, MACIEJ1 bendkowski@tcs.uj.edu.pl, GRYGIEL, KATARZYNA1 grygiel@tcs.uj.edu.pl, ZAIONC, MAREK1 zaionc@tcs.uj.edu.pl
Source: Journal of Logic & Computation. Oct2017, Vol. 27 Issue 7, p2251-2269. 19p.
Subjects: Combinatory logic, Likelihood ratio tests, Asymptotic normality, Lambda calculus, Mathematical notation
Abstract: We present a quantitative basis-independent analysis of combinatory logic. Using a general argument regarding plane binary trees with labelled leaves, we generalize the results of David et al. (see [11]) and Bendkowski et al. (see [6]) to all Turing-complete combinator bases proving, inter alia, that asymptotically almost no combinator is strongly normalizing nor typeable. We exploit the structure of recently discovered normal-order reduction grammars (see [3]) 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 the set of normalizing combinators. We show that the density of normalizing combinators cannot be less than 34%, improving the previously best lower bound of approximately 3% (see [6]). Finally, we present some super-computer experimental results, conjecturing that the density of the set of normalizing combinators is close to 85%. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:We present a quantitative basis-independent analysis of combinatory logic. Using a general argument regarding plane binary trees with labelled leaves, we generalize the results of David et al. (see [11]) and Bendkowski et al. (see [6]) to all Turing-complete combinator bases proving, inter alia, that asymptotically almost no combinator is strongly normalizing nor typeable. We exploit the structure of recently discovered normal-order reduction grammars (see [3]) 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 the set of normalizing combinators. We show that the density of normalizing combinators cannot be less than 34%, improving the previously best lower bound of approximately 3% (see [6]). Finally, we present some super-computer experimental results, conjecturing that the density of the set of normalizing combinators is close to 85%. [ABSTRACT FROM AUTHOR]
ISSN:0955792X
DOI:10.1093/logcom/exx005