Chaitin's constant for lambda calculus and combinatory logic

161 Views Asked by At

I have found some approximations of Chaitin's Constant for turing machines but I have not found approximations for others. I'd like to have a rough estimate or upper bound on it for lambda calculus and combinatory logic. I expect it to be very low as is the case with turing machines. For context I am exploring recursion in genetic programing and a major point I'd like to make is that most programs don't halt so there is a huge gain by only considering the programs which do halt. While I think most people would agree with this I'd like to have a more formal argument. Because I am using combinatory logic for my programs I'd prefer a Chaitin constant for combinatory logic. If the probability is very low it lends weight to my point. If it is somehow high I would be very surprised and rethink the idea.

Does anyone know of such approximations? If not for lambda calculus and/or combinatory logic what about for other models of computation which are not turing machines?

1

There are 1 best solutions below

0
On BEST ANSWER

This might be relevant:

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.

From Asymptotically almost all λ-terms are strongly normalizing.