Hostname: page-component-76fb5796d-wq484 Total loading time: 0 Render date: 2024-04-25T09:38:18.096Z Has data issue: false hasContentIssue false

Statistical properties of simple types

Published online by Cambridge University Press:  10 November 2000

M. MOCZURAD
Affiliation:
Computer Science Department, Jagiellonian University, Nawojki 11, 30-072 Krakow, Poland. Email madry@softlab.ii.uj.edu.pl; zaionc@ii.uj.edu.pl
J. TYSZKIEWICZ
Affiliation:
Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland, Email jty@mimuw.edu.pl on leave at School CSE, UNSW, 2052 Sydney, Australia
M. ZAIONC
Affiliation:
Computer Science Department, Jagiellonian University, Nawojki 11, 30-072 Krakow, Poland. Email madry@softlab.ii.uj.edu.pl; zaionc@ii.uj.edu.pl

Abstract

We consider types and typed lambda calculus over a finite number of ground types. We are going to investigate the size of the fraction of inhabited types of the given length n against the number of all types of length n. The plan of this paper is to find the limit of that fraction when n → ∞. The answer to this question is equivalent to finding the ‘density’ of inhabited types in the set of all types, or the so-called asymptotic probability of finding an inhabited type in the set of all types. Under the Curry–Howard isomorphism this means finding the density or asymptotic probability of provable intuitionistic propositional formulas in the set of all formulas. For types with one ground type (formulas with one propositional variable), we prove that the limit exists and is equal to 1/2 + √5/10, which is approximately 72.36%. This means that a long random type (formula) has this probability of being inhabited (tautology). We also prove that for every finite number k of ground-type variables, the density of inhabited types is always positive and lies between (4k + 1)/(2k + 1)2 and (3k + 1)/(k + 1)2. Therefore we can easily see that the density is decreasing to 0 with k going to infinity. From the lower and upper bounds presented we can deduce that at least 1/3 of classical tautologies are intuitionistic.

Type
Research Article
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)