# When does the function mapping a string to its prefix-free Kolmogorov complexity halt?

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?

• 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).
– Vor
Jul 5 '12 at 9:18
• @Vor: This is certainly another valid interpretation (given the information we have). You should post this as an answer.
– Raphael
Jul 5 '12 at 9:24
• @Raphael: ok, posted as an answer; if I find the book I'll give it a look.
– Vor
Jul 5 '12 at 9:33
• @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.
– Juho
Jul 5 '12 at 11:09
• @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
– Vor
Jul 5 '12 at 14:17

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.

$\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$.

• 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. Jul 6 '12 at 11:04
• @CarlMummert: I have seen the notation for both things. In particular in the realm of partially-computable functions, undefinedness and nontermination are usually equivalent.
– Raphael
Jul 6 '12 at 11:43
• 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. Jul 6 '12 at 13:29
• I think you're right, Carl, it might be the correct answer. Jul 8 '12 at 7:06