4 ms·

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

• eru 17y ago
  Look at primitive recursive functions. E.g. see http://en.wikipedia.org/wiki/Primitive_recursive_function http://en.wikipedia.org/wiki/Primitive_recursive_function
  • jey 17y ago
    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.
    • eru 17y ago
      That might be possible. Primitive recursion is much less powerful than Turing machines.