<p>You probably want to look at David <em>et al</em>'s paper, <a href="http://arxiv.org/pdf/0903.5505" rel="noreferrer">Asymptotically Almost All λ-terms are Strongly Normalizing</a>:</p>
<blockquote>
<p>We present a quantitative analysis of various (syntactic and behavioral) properties of random λ-terms. Our main results show that asymptotically, <strong>almost all terms are strongly normalizing</strong> and that any fixed closed term almost never appears in a random term.</p>
<p><strong>Surprisingly, in combinatory logic (the translation of the λ-calculus into combinators), the result is exactly opposite.</strong> 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.</p>
</blockquote>
<p>You should be able to cook up a bound from looking at the details of their proof.</p>

CC BY-SA 3.0
2014-06-03T13:57:52.887Z
Thanks! That is exactly what I wanted! Could not not have been a better response.
Jake
CC BY-SA 3.0
2014-06-02T13:09:37.840Z
2014-06-02T13:09:37.840Z
2020-06-17T09:38:08.363Z
Neel Krishnaswami
<p>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?</p>

<p>I also found <a href="http://en.wikipedia.org/wiki/Binary_lambda_calculus#Halting_probability">this</a> 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?</p>

<pr.probability><lambda-calculus><combinatory-logic>
Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic
Jake
# Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic

(Asked by: username_0 on 2014-06-02)

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](http://en.wikipedia.org/wiki/Binary_lambda_calculus#Halting_probability) 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?

**Tags:** pr.probability, lambda-calculus, combinatory-logic

---

## 1 answers

### Answer by username_1 on 2014-06-02. Score: 10 | Accepted answer

You probably want to look at David *et al*'s paper, [Asymptotically Almost All λ-terms are Strongly Normalizing](http://arxiv.org/pdf/0903.5505):

> 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.

> **Comments:**
> **username_0**: Thanks! That is exactly what I wanted! Could not not have been a better response.  

---

