Welcome to MathOverflow

Question

0

1

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.

edited Jul 6 2011 at 8:23

asked Jul 5 2011 at 17:17

Ghassen Hamrouni
21●3

2

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 2011 at 17:47

2

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 2011 at 22:15

2

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 2011 at 0:44

Thanks for the comments, I edited my question. – Ghassen Hamrouni Jul 6 2011 at 8:26

2

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 2011 at 15:05

show 1 more comment

Calculating bounds of kolmogorov complexity.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.