Ich suche nach einem Beweis dafür, dass die Komplexität von Kolmogorov nicht berechenbar ist, indem ich ein anderes nicht berechenbares Problem reduziere. Der übliche Beweis ist eher eine Formalisierung von Berrys Paradoxon als eine Reduktion, aber es sollte einen Beweis geben, indem man von etwas wie dem Halteproblem oder dem Korrespondenzproblem der Post reduziert.
computability
reductions
kolmogorov-complexity
Krishna Chikkala
quelle
quelle
Es war eine lustige Frage, darüber nachzudenken. Wie in der anderen Antwort und den Kommentaren unten beschrieben, gibt es eine Turing-Reduzierung vom Halting-Problem zur Berechnung der Kolmogorov-Komplexität, aber insbesondere gibt es keine solche Reduzierung von vielen, zumindest für eine Definition der "Berechnung der Kolmogorov-Komplexität".
Lassen Sie uns formal definieren, wovon wir sprechen. Es sei die Standardsprache von TMs, die anhalten, wenn eine Beschreibung ihrer selbst als Eingabe gegeben wird. Lassen K O bezeichnen { ⟨ x , k ⟩ | x hat Kolmogorov Komplexität genau k } .HALT KO {⟨x,k⟩∣x has Kolmogorov complexity exactly k}
Es sei angenommen, dass durch eine Reduktion um viele ist. Sei f : { 0 , 1 } ∗ → { 0 , 1 } ∗ die Funktion, die diese Reduktion berechnet. Betrachten Sie das Bild von H A L T unter f , das ich mit f ( H A L T ) bezeichnen werde .H.A L T.≤ K.Ö f:{0,1}∗→{0,1}∗ HALT f f(HALT)
Hinweis besteht aus Ketten von der Form ⟨ x , k ⟩ wo x Kolmogorov - Komplexität hat genau k . Ich behaupte, dass die ks , die in f ( H A L T ) vorkommen, unbegrenzt sind, da es nur eine endliche Anzahl von Strings mit Kolmogorov-Komplexität genau k gibt und f ( H A L T ) unendlich ist.f(HALT) ⟨x,k⟩ x k k f(HALT) k f(HALT)
Da rekursiv aufzählbar ist (in einigen Büchern auch als Turing erkennbar), folgt, dass f ( H A L T ) rekursiv aufzählbar ist. In Verbindung mit der Tatsache , dass die k ‚s sind unbegrenzt, können wir aufzählen f ( H A L T ) , bis wir einige finden ⟨ x , k ⟩ mit k so groß , wie wir wollen; dh es existiert eine TM M , dass am Eingang k ausgibt , ein Element ⟨ x , k ⟩HALT f(HALT) k f(HALT) ⟨x,k⟩ k M k .⟨x,k⟩∈f(HALT)
Schreiben Sie ein neues TM , das Folgendes ausführt: Berechnen Sie zuerst | M ' | unter Verwendung des Rekursionssatzes von Kleene. Abfrage M mit Eingabe | M ' | + 1 erhalten ⟨ x , | M ' | + 1 ⟩ ∈ F ( H A L T ) . Ausgabe x .M′ |M′| M |M′|+1 ⟨x,|M′|+1⟩∈f(HALT) x
Klar , dass die Ausgabe von M ' ist eine Zeichenkette mit Kolmogorov Komplexität höchstens | M ' | aber ⟨ x , | M ' | + 1 ⟩ ∈ F ( H A L T ) , die ein Widerspruch.x M′ |M′| ⟨x,|M′|+1⟩∈f(HALT)
Ich glaube, Sie können auch das Problem "Kolmogorov-Komplexität genau " durch "Kolmogorov-Komplexität mindestens k " mit geringfügigen Änderungen ersetzen .k k
quelle