most recent 30 from http://mathoverflow.net 2013-05-21T22:24:13Z http://mathoverflow.net/feeds/question/69550 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69550/calculating-bounds-of-kolmogorov-complexity Ghassen Hamrouni 2011-07-05T17:17:33Z 2011-07-06T08:23:10Z

<p>There has been some sucesseful attempts to to calculate the initial values or lower bounds of some non computable functions like the <a href="http://mathworld.wolfram.com/BusyBeaver.html" rel="nofollow">busy beaver function</a>.</p> <p>It is known that we cannot calculate the exact value of the <a href="http://mathworld.wolfram.com/KolmogorovComplexity.html" rel="nofollow">kolmogorov complexity</a>, but we can find an upper bound and a lower bound.</p> <p>I'm wondering if there has been some attempts to calculate a finer bounds of the kolmogorov complexities for some non trivial cases.</p>