Re:9,73,241,561,1081,1849,_?_
by eru on Thursday November 05, 2009 @05:27PM
(#924930)
It's only difficult in general. Nobody says there aren't any easy instances.
[ Parent
| on HN ]
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.