Re:9,73,241,561,1081,1849,_?_
by jey on Thursday November 05, 2009 @03:59PM
(#924754)
It only takes a counter-example (an example of a shorter program) to show that an answer is incorrect, but you could probably pick up a Turing Award or two if you find a way to put a tight bound on the Kolmogorov complexity of a bit string.
[ Parent
| on HN ]
It's only difficult in general. Nobody says there aren't any easy instances.
Sure, there's a bunch of trivial/easy ones for programs that do almost nothing, but I really wonder if are there any interesting programs for which tight bounds are known?
Look at primitive recursive functions.
E.g. see http://en.wikipedia.org/wiki/Primitive_recursive_function
Even if we limit it to primitive recursive functions, how can we put a bound on the Kolmogorov complexity of one? We'd need some way of coming up with bounds on the smallest Turing machine to compute that function.