4
$\begingroup$

In Algorithmic Randomness and Complexity from Downey and Hirschfeldt, it is stated on page 129 that

$\qquad \displaystyle \sum_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$,

where $K(\sigma)\downarrow$ means that $K$ halts on $\sigma$, $\sigma$ being a binary string. $K$ denotes the prefix-free Kolmogorov complexity.

When does $K$ halt? I think it only halts on a finite number of inputs, since the classical proof on non-computability of the Kolmogorov complexity gives an upper bound on the domain of $K$. But then, the finite set of inputs on which $K$ halts can be chosen arbitrary (one just needs to store the finite number of complexities in the source code).

So is this sum well-defined? In other words, is the domain of $K$ well defined?

$\endgroup$
  • $\begingroup$ as commented in Raphael's answer below if $K$ is the prefix-free Kolmogorov complexity then it is a partial function (it is not defined on strings that are not prefix-free); so I think that the sum is well defined and $K(\sigma)\downarrow$ simply means "$K(\sigma)$ is defined" (i.e. $\sigma$ is a prefix-free string). $\endgroup$ – Vor Jul 5 '12 at 9:18
  • $\begingroup$ @Vor: This is certainly another valid interpretation (given the information we have). You should post this as an answer. $\endgroup$ – Raphael Jul 5 '12 at 9:24
  • $\begingroup$ @Raphael: ok, posted as an answer; if I find the book I'll give it a look. $\endgroup$ – Vor Jul 5 '12 at 9:33
  • 1
    $\begingroup$ @Vor This seems to be some early(?) version of the book. The claim of the OP didn't catch my eye, maybe it's on a different page or doesn't even exist in this early version. $\endgroup$ – Juho Jul 5 '12 at 11:09
  • $\begingroup$ @Juho: see Counting Theorem and Definition 6.7.5 (page 103) where it is shown that $K$ is equal (up to a costant) to the minimal information content measure $\endgroup$ – Vor Jul 5 '12 at 14:17
1
$\begingroup$

I think you are right; $K$ is a specific function which can not be computed. The author likely means to use some (arbitrary) approximative implementation; so no, this does not seem to be well-defined, if you are pedantic. You can also call it abuse of notation.

Consider this instead:

$\qquad \displaystyle \forall {M \in \mathcal{M}_K}.\ \sum_{M(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$

with $\mathcal{M}_K = \{M\ \mathrm{TM} \mid M(\sigma)\!\downarrow\ \implies\ M(\sigma)=K(\sigma) \}$ the set of all Turing machines that compute subfunctions of $K$.

In essence, this means: the bound holds no matter for which strings your implementation can compute the Kolmogorov complexity.


As Carl notes in the comments, it is plausible that the notation has nothing to do with halting or computing, as $K$ is not computable. Read $\sum_{K(\sigma)\!\downarrow}$ as sum ranging over the domain of $K$.

$\endgroup$
  • $\begingroup$ I seriously doubt this is what they meant. The $\downarrow$ notation for a partial function has nothing to do with halting, in general, it just means the partial function is defined. $\endgroup$ – Carl Mummert Jul 6 '12 at 11:04
  • $\begingroup$ @CarlMummert: I have seen the notation for both things. In particular in the realm of partially-computable functions, undefinedness and nontermination are usually equivalent. $\endgroup$ – Raphael Jul 6 '12 at 11:43
  • $\begingroup$ That's true, they are equivalent in that special case. But $K$ is not partial computable, so that special case can't apply here. In fact $K$ is total, although not computable. $\endgroup$ – Carl Mummert Jul 6 '12 at 13:29
  • $\begingroup$ I think you're right, Carl, it might be the correct answer. $\endgroup$ – pintoch Jul 8 '12 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.