3 ms·

Well my contention is that K(x) is constant, in fact K(x) = 0. The problem with fixing L is that it 'biases' the complexity based on the language chosen.

• shasta 13y ago
  That bias with a fixed L is present, but you already mentioned the answer in your article: the difference is bounded. Compare to the situation with algorithm complexity. We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. We instead introduce Big-Oh and agree to ignore the differences in constants.
  • gwern 13y ago
    > We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. Unless you're Knuth!
  • Ono-Sendai 13y ago
    The difference is not really bounded in a meaningful way. The bound is large enough that the complexity can go to zero in some language.