Marek Zaionc (UJ)
Asymptotic densities 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 term or finally random combinatory logic terms. Our main goal is to investigate likelihood of semantic properties of random computational objects.

For the given logical calculus we investigate the proportion of the number of distinguished formulas (or types or terms of a certain calculus) of length n to the number of all objects of such length. We are interested in asymptotic behavior of this fraction when length n tends to infinity. For the given set A of objects the limit l(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:
1. How big is the fraction of one logic being sub-logic of the bigger one based onthe same language?
2. Estimate the chances that random formula is true or how big is the fraction of tautologies?
3. What are chances that random program terminates?

Możliwość komentowania jest wyłączona.