Gibt es x mit K (xx) <K (x), wobei K die Kolmogorov-Komplexität ist?

16

Sei die Kolmogorov-Komplexität einer Zeichenkette x . Haben gibt es eine Zeichenfolge , so dass K ( x x ) < K ( x ) . (Hier ist x x die Verkettung von x mit sich selbst). Eine ähnliche, aber unterschiedliche Frage wurde hier gestellt , aber das in der Antwort auf diese Frage angegebene Gegenbeispiel funktioniert für diese Frage nicht.K(x)xK(xx)<K(x)xxx

Sune Jakobsen
quelle

Antworten:

20

Ich bin kein Experte für Kolmogorov-Komplexität, aber ich denke, dass ein solches x für jede Komplexitätsfunktion K wie folgt konstruiert werden kann. Da 1, 11, 1111, 11111111,…, 1 2 n ,… eine Kodierung einer natürlichen Zahl n ist , kann K (1 2 n ) nicht o (log n ) sein. Wenn jedoch n = 2 m ist , ist offensichtlich K (1 2 n ) = K (1 2 2 m ) = O (log m ) = O (log log n ). Daher kann die Sequenz K (1), K (11), K (1111), K (11111111), ..., K (1 2 n ), ... nicht schwach monoton ansteigen, was bedeutet, dass eine Kette existiertx in der Form 1 2 n, so dass K ( xx ) <K ( x ) ist.

Tsuyoshi Ito
quelle
1
@ Tsuyoshi, Gibt es eine inkompressible Zeichenkette so dass K ( x x ) < K ( x ) ist ? xK(xx)<K(x)
Mohammad Al-Turkistany
Ich denke, dass und K (1 ^ {2 ^ n}) = Ω (log n) sich widersprechen. Was er meint ist: Wenn f ( n ) = o ( log n ), dann ist K ( 1 2 n ) O ( f ( n ) ) . Ansonsten scheint der Beweis in Ordnung. K(122m)=O(logm)f(n)=o(logn)K(12n)O(f(n))
Sune Jakobsen
1
Das scheint zu funktionieren. In der Tat denke ich, es gibt Ihnen eine unendliche Folge solcher Zeichenfolgen. Entweder verstehe ich jedoch etwas falsch oder die Aussage der Kettenregel für Kolmogorov-Komplexität, die in Wikipedia ( en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity ) erscheint, ist dann falsch. Anfangs dachte ich, dass die Definition von Wikipedia hier nicht zutreffen könnte, da man wissen muss, wo X endet und Y beginnt, während dies hier nicht erforderlich zu sein scheint, aber wenn Y = X, kann man das der Beschreibung in hinzufügen O (1) mit "Split in the Middle".
Abel Molina
@Sune: Die Notation Ω (⋅) hat einige leicht unterschiedliche Definitionen. "K (1 ^ 2 ^ n) = Ω (log n)" in meiner Antwort bedeutet "limsup K (1 ^ 2 ^ n) / log n> 0" und widerspricht nicht "K (1 ^ 2 ^ 2" ^ m) = O (log m). “Ich habe die Antwort bearbeitet, um diesen Punkt zu verdeutlichen. Siehe auch Welche Definition der asymptotischen Wachstumsrate sollten wir vermitteln?
Tsuyoshi Ito
1
@turkistany und alle: Beachten Sie, dass es immer wahr ist, dass K (xx)> K (x) -c für eine Konstante, ich dachte, dies sollte darauf hingewiesen werden. Dies bedeutet auch, dass wir eine sehr genaue Definition von inkompressibel benötigen, wenn wir diese Frage untersuchen wollen. Ich würde vermuten, dass die Antwort wieder Ja lautet, aber ich habe keinen Beweis.
Domotorp
2

Ja. Die Komplexität von Kolomogorov in der Praxis hängt von Ihrem Modell ab. Turing-Maschine, Java-Programm, C ++ - Programm, ... Wenn Ihr Modell eine Eigenart aufweist, die dies für eine begrenzte Anzahl von Eingaben zulässt, ist dies kein Problem.

Die bessere Frage ist, mit wie viel von diesem Verhalten Sie durchkommen und das Modell dennoch universell sein lassen können.

Chad Brewbaker
quelle
Ich denke, eine bessere Frage ist: Gibt es ein solches x für alle Modelle? Ich weiß nicht, was ein "Modell" formal ist, aber es scheint, dass Tsuyoshis Antwort für alle vernünftigen Programmiersprachen funktioniert.
Sune Jakobsen
0xxx
1

@ Tsuyoshi:

Ich habe deinen Beweis nicht gut verstanden.

K(s) s

TMssss=1111...1=12n+1TMss=12n

Kann Ihr Beweis auf die Komplexität von Kolmogorov auf TMs angewendet werden?

n+1=2mTMssTMsn

(Entschuldigung, aber ich weiß nicht, wie ich das als Kommentar posten soll)

Marzio De Biasi
quelle
Um einen Kommentar zu einem Beitrag von jemand anderem als Ihnen zu verfassen , der keine Antwort auf Ihre Frage darstellt, benötigen Sie einen Rufpunkt von mindestens 50.
Tsuyoshi Ito