7
$\begingroup$

I'd like to have proof that Chaitin's constant for lambda calculus and/or SKI combinatory logic is pretty small. I've found some approximations (accurate to about 63 binary digits) for truing machines and as expected they were low, below 1% in fact. I can't find any bounds for lambda calculus or combinatory logic. I'd really just like to show that it is less than 10% to 20%. Does anyone know of such a paper or how to get such an awnser?

I also found this but it doesn't have a reference for how it got that answer. If correct it would show that the probability is between 0.125 and 0.0625 which is great for me! Does anyone have a citation for this?

$\endgroup$
9
$\begingroup$

You probably want to look at David et al's paper, Asymptotically Almost All λ-terms are Strongly Normalizing:

We present a quantitative analysis of various (syntactic and behavioral) properties of random λ-terms. Our main results show that asymptotically, almost all terms are strongly normalizing and that any fixed closed term almost never appears in a random term.

Surprisingly, in combinatory logic (the translation of the λ-calculus into combinators), the result is exactly opposite. We show that almost all terms are not strongly normalizing. This is due to the fact that any fixed combinator almost always appears in a random combinator.

You should be able to cook up a bound from looking at the details of their proof.

$\endgroup$
  • $\begingroup$ Thanks! That is exactly what I wanted! Could not not have been a better response. $\endgroup$ – Jake Jun 3 '14 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.