Marek Zaionc, Jagiellonian University, Poland


Asymptotic density in logic and computability


This talk presents numerous results from the area of quantitative investigations in logic and computability. We present a quantitative analysis of random formulas or random lambda terms or random combinatory logic terms. Our main goal is to investigate likelihood of semantic properties of random computational objects. For the given logical calculus (or type theory or combinatory logic term) we investigate the proportion of the number of distinguished formulas (or types or terms) of a certain length $n$ to the number of all formulas of such length. We are especially interested in asymptotic behavior of this fraction when $n$ tends to infinity. For the given set $A$ of objects the limit $\mu(A)$ if exists, is an asymptotic probability of finding formula from the class $A$ among all formulas or may also be interpreted as the asymptotic density of the set $A$. Results obtained are having some philosophical flavor like for example: