Qué hacer el mapa de la función de una cadena a su complejidad Kolmogorov detuvo sin prefijo?

Question

Algorítmica y Complejidad aleatoriedad de Downey y Hirschfeldt, se afirma en la página 129 que

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

donde K $ (\ sigma) \ downarrow $ significa que $ K $ detiene en $ \ sigma $, $ \ sigma $ siendo una cadena binaria. $ K $ denota la complejidad de Kolmogorov sin prefijo.

¿Cuándo $ K $ punto muerto? Creo que sólo se detiene en un número finito de entradas, ya que la prueba clásica en la no computabilidad de la complejidad de Kolmogorov da un límite superior en el dominio de $ K $. Pero entonces, el conjunto finito de entradas en los cuales $ K $ paradas se pueden elegir arbitraria (uno sólo necesita almacenar el número finito de complejidades en el código fuente).

Así es esta suma bien definido? En otras palabras, es el dominio de $ K $ bien definido?

Answer 1

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