Quand la fonction mappage d'une chaîne à la complexité de Kolmogorov préfixe sans arrêt?

Question

Algorithmique et complexité Hasard de Downey et Hirschfeldt, il est dit à la page 129 que

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

où K $ (\ sigma) \ downarrow moyen de $ qui arrête $ K $ sur $ \ sigma $, $ \ sigma $ étant une chaîne binaire. $ K $ désigne la complexité de Kolmogorov sans préfixe.

Quand est-halt $ K $? Je pense que seulement un arrêt sur un nombre fini d'entrées, puisque la preuve classique sur la non-calculabilité de la complexité de Kolmogorov donne une borne supérieure sur le domaine de $ K $. Mais alors, l'ensemble fini d'entrées sur laquelle K $ arrêts de $ peuvent être choisis arbitrairement (on a juste besoin de stocker le nombre fini de complexité du code source).

est cette somme bien définie? En d'autres termes, est le domaine de $ K $ bien définie?

Answer 1

Je pense que vous avez raison; $ K $ est une fonction spécifique qui ne peut être calculée. L'auteur de moyens susceptibles d'utiliser certains (arbitraire) la mise en œuvre approximative; donc pas, cela ne semble pas être bien définie, si vous êtes pédant. Vous pouvez également appeler abus de notation.

Considérez ceci:

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

avec $ \ mathcal {M} _K = \ {M \ \ mathrm {TM} \ mid M (\ sigma) \! \ Downarrow \ \ implique \ M (\ sigma) = K (\ sigma) \} $ l'ensemble de toutes les machines de Turing que les sous-fonctions de calcul de $ K $.

En substance, cela signifie:. La limite tient peu importe pour laquelle des chaînes de votre mise en œuvre peut calculer la complexité de Kolmogorov

---

Comme le note Carl dans les commentaires, il est plausible que la notation n'a rien à voir avec arrêter ou de calcul, comme $ K $ est pas calculable. Lire $ \ sum_ {K (\ sigma) \! \ Downarrow} $ comme somme allant sur le domaine de $ K $.