Wann hält die Funktion, die eine Zeichenfolge in die Präfixfreiheit der Komplexität der Kolmogorov-Komplexität zuordnet, an?

Question

Im Algorithmische Zufälligkeit und Komplexität Von Downey und Hirschfeldt wird auf Seite 129 angegeben, dass

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

wobei $ k ( sigma) Downarrow $ bedeutet, dass $ k $ auf $ sigma $ $ $ sigma $ ein binärer String ist. $ K $ bezeichnet die Präfix-freie Kolmogorov-Komplexität.

Wann hält $ k $ an? Ich denke, es hält nur eine begrenzte Anzahl von Eingaben an, da der klassische Beweis für die Nichtberechnung der Kolmogorov-Komplexität eine Obergrenze für die Domäne von $ k $ liefert. Aber die endlichen Eingänge, für die $ K $ Haltsbitträr ausgewählt werden kann (man muss nur die endliche Anzahl von Komplexitäten im Quellcode speichern).

Ist diese Summe gut definiert? Mit anderen Worten, ist die Domain von $ k $ gut definiert?

Answer 1

Ich glaube, Du hast recht; $ K $ ist eine bestimmte Funktion, die nicht berechnet werden kann. Der Autor bedeutet wahrscheinlich zu verwenden etwas (willkürliche) ungefähre Umsetzung; Nein, das scheint nicht definiert zu sein, wenn Sie pedantisch sind. Sie können es auch Missbrauch der Notation nennen.

Betrachten Sie dies stattdessen:

$ qquad displayStyle forall {m in mathcal {m} _k}. sum_ {m ( sigma) downarrow} 2^{-k ( sigma)} leq 1 $

mit $ mathcal {m} _k = {m mathrm {tm} mid m ( sigma) ! downarrow implements m ( sigma) = k ( sigma) } $ das Set von der Set von von Alle Turing -Maschinen, die Unterfunktionen von $ k $ berechnen.

Im Wesentlichen bedeutet dies: Die gebundene hält unabhängig davon, welche Zeichenfolgen Ihre Implementierung die Kolmogorov -Komplexität berechnen kann.

---

Wie Carl in den Kommentaren feststellt, ist es plausibel, dass die Notation nichts mit Stoppen oder Berechnen zu tun hat, da $ K $ nicht berechnet werden kann. Lesen Sie $ sum_ {k ( sigma) ! Downarrow} $ als Summe über die Domäne von $ k $.