Quando ha la funzione di mappatura di una stringa per il suo libero-prefix complessità di Kolmogorov battuta d'arresto?

Question

algoritmica casualità e Complessità da Downey e Hirschfeldt, si precisa a pagina 129 che

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

dove $ K (\ sigma) \ downarrow $ significa che $ K $ ferma su $ \ sigma $, $ \ sigma $ è una stringa binaria. $ K $ denota la libera-prefix complessità di Kolmogorov.

Quando si fa $ K $ battuta d'arresto? Penso che sia solo ferma su un numero finito di ingressi, dal momento che la prova classica sulla non-computabilità della complessità di Kolmogorov dà un limite superiore sul dominio di $ K $. Ma poi, l'insieme finito di ingressi di cui $ K $ soste possono essere scelti arbitrariamente (uno deve solo memorizzare il numero finito di complessità nel codice sorgente).

Quindi è questa somma ben definita? In altre parole, è il dominio di $ K $ ben definito?

Answer 1

Credo che tu abbia ragione; $ K $ è una funzione specifica che non può essere calcolato. L'autore mezzi propensi a usare alcuni (arbitrario) realizzazione approssimativa; quindi no, questo non sembra essere ben definito, se siete pedanti. È anche possibile chiamare un abuso di notazione.

Si consideri questo, invece:

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

con $ \ mathcal {M} _K = \ {M \ \ mathrm {TM} \ metà M (\ sigma) \! \ Downarrow \ \ implica \ M (\ sigma) = K (\ sigma) \} $ l'insieme di tutte le macchine di Turing che funzioni parziali di elaborazione di $ K $.

In sostanza, questo significa che:. Il limite vale non importa per quale stringhe l'implementazione in grado di calcolare la complessità di Kolmogorov

---

note come Carl nei commenti, è plausibile che la notazione non ha nulla a che fare con arresto o di calcolo, da $ K $ non è calcolabile. Leggi $ \ sum_ {K (\ sigma) \! \ Downarrow} $ come somma che vanno oltre il dominio di $ K $.