5
$\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?

Improve this question
$\endgroup$
8
  • $\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 14:17

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
4
  • $\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, 2012 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, 2012 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, 2012 at 13:29
  • $\begingroup$ I think you're right, Carl, it might be the correct answer. $\endgroup$
    – pintoch
    Jul 8, 2012 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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