News for hackers. Stuff that matters.
Re:9,73,241,561,1081,1849,_?_ by jey on Thursday November 05, 2009 @05:39PM (#924947)
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?
Re:9,73,241,561,1081,1849,_?_ by eru on Thursday November 12, 2009 @11:08PM (#939342)
Look at primitive recursive functions.

E.g. see http://en.wikipedia.org/wiki/Primitive_recursive_function

Re:9,73,241,561,1081,1849,_?_ by jey on Friday November 13, 2009 @01:13PM (#940434)
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.
Re:9,73,241,561,1081,1849,_?_ by eru on Friday November 27, 2009 @08:46PM (#964681)
That might be possible. Primitive recursion is much less powerful than Turing machines.