# Calculating bounds of kolmogorov complexity.

There has been some sucesseful attempts to to calculate the initial values or lower bounds of some non computable functions like the busy beaver function.

It is known that we cannot calculate the exact value of the kolmogorov complexity, but we can find an upper bound and a lower bound.

I'm wondering if there has been some attempts to calculate a finer bounds of the kolmogorov complexities for some non trivial cases.

-
There enough detail here to answer the question. Moreover, Kolmogorov complexity of strings or natural numbers is only ever defined up to an additive constant. –  Carl Mummert Jul 5 '11 at 17:47
Dear Ghassen: As Carl pointed out, this question is lacking in many ways. I suggest you read mathoverflow.net/howtoask and then reformulate your question appropriately. Once you have done that, edit your question and flag for moderator attention so it can be reopened for answers. –  François G. Dorais Jul 5 '11 at 22:15
I believe that the question could be improved and re-opened. I would look upon it as asking for something like we have in the situation with known values or lower bounds of the busy beaver function. One could hope to do a similar thing with Kolmogorov complexity, having fixed a specific notion of complexity via a specific model of computation, by computing bounds on the complexity for small cases. –  Joel David Hamkins Jul 6 '11 at 0:44
Thanks for the comments, I edited my question. –  Ghassen Hamrouni Jul 6 '11 at 8:26
For any string there is a universal prefix-free code that gives the string complexity exactly 1, and for any $n$ there is a code that gives the string complexity exactly $n$. So one cannot really compute upper bounds, and the lower bounds are trivial. On the other hand there is this paper by Calude, Dinneen, and Shu: www.expmath.org/expmath/volumes/11/11.3/Calude361_370.pdf . Is that the sort of thing you are looking for? –  Carl Mummert Jul 6 '11 at 15:05
show 1 more comment