Some properties of random -terms ∗

摘要: AbstractWe present quantitative analysis of various (syntactic and behavioral)properties random  -terms. Our main results are that asymptotically allthe terms strongly normalizing any xed closed t erm almost neverappears in a term. Surprisingly, combinatory logi c (the translationof the -calculus into combinators) result is exactly opposite . We showthat all not normalizing. This due to fact thatany combinator always appears combin ator.Keywords: -calculus, strong normalization, randomness, y logic. 1 Introduction Since pioneering works Church, Turing et al. , more than 70 years ago, widerange computational models have been introduced. It turn s out they areall equivalent what can compute. However, this equivalence says nothingabout do typical programs or machines each these models.This paper addresses following question. Having (theo retical) program-ming language property, probability r andom programsatis es given property? In particular, it true lmost every randomprogram satis desired property.We concentrate on functional programming languages and, mo re speci cally, onthe simplest such (see [9, 11, 14] for si milar othermodels computation). The only work we found th subject someexperiments made by Jue Wang [16]). Most interesting pr operties arethose concerning their behavior. analyze them, one has considersome syntactic properties as well.As far know, no asymptotic value number -terms size n isknown. give Section 6) upper lower bounds (super-exponential)number. Although gap between boun d big (expo-nential), estimations sucient our purpose.