Der Beweis für die Komplexität von Kolmogorov ist mit Reduktionen nicht berechenbar

9

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.

Krishna Chikkala
quelle

Antworten:

11

Sie finden zwei verschiedene Beweise in:

Gregory J. Chaitin, Cristian Calude, Asat Arslanov: Komplexität in Programmgröße berechnet das Halteproblem. Bulletin des EATCS 57 (1995)

In Li, Ming, Vitányi, Paul MB; Eine Einführung in die Kolmogorov-Komplexität und ihre Anwendungen wird als Übung vorgestellt (mit einem Hinweis zur Lösung, der P. Gács von W. Gasarch in einer persönlichen Mitteilung vom 13. Februar 1992 zugeschrieben wird).

** Ich habe beschlossen, eine erweiterte Version davon in meinem Blog zu veröffentlichen .

Marzio De Biasi
quelle
1
Darüber hinaus zeigt Chaitins Beweis (in diesem Link), dass die Orakelabfragen parallel durchgeführt werden können.
Sind diese Beweise wirklich Turning-Reduktionen (eins zu eins (oder) eins zu viele)? Ich bin verwirrt !! Bitte helfen Sie mir
Krishna Chikkala
@KrishnaChikkala: Das erste ist sicherlich eine Turing-Reduktion . Ich fand es nicht so klar und beschloss , eine erweiterte Version davon in meinem Blog zu veröffentlichen . Wenn Sie es sich ansehen möchten (und mir per E-Mail mitteilen, ob Sie der Meinung sind, dass es verbessert werden kann). Beachten Sie auch, dass sich Turing-Reduzierungen von Mehrfachreduzierungen (die "stärkere" Reduzierungen sind) unterscheiden. in der Tat beweist die Antwort von Joe Bebel, dass eine solche Reduzierung nicht existieren kann.
Marzio De Biasi
7

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 } .HALTKO{x,kx 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.EINL.T.K.Öf:{0,1}{0,1}HALTff(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,kxkkf(HALT)kf(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 HALTf(HALT)kf(HALT)x,kkMk .x,kf(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|+1x,|M|+1f(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.xM|M|x,|M|+1f(HALT)

Ich glaube, Sie können auch das Problem "Kolmogorov-Komplexität genau " durch "Kolmogorov-Komplexität mindestens k " mit geringfügigen Änderungen ersetzen .kk

Joe Bebel
quelle
1
Aber was ist mit einer Turing-Reduzierung?
Sasho Nikolov
Lassen Sie mich diese Idee in einem Kommentar verwerfen, weil ich die Idee nicht durchdacht habe. Lassen Sie die Entscheidungsprobleme das gleiche sein , aber die Reduktion ist jetzt eine Turing Reduktion . Betrachte die Menge S aller x , k K O , so daß es einige TM in existiert H A L T die bewirkt , dass R die zur Abfrage K O Oracle auf Eingangs x , k K O . Ich behaupte, S hat das gleiche unbegrenzte kRSx,kKOHALTRKOx,kKOSkEigenschaft (dies muss ein bisschen mehr gerechtfertigt werden , als ich unter Angabe bin) und kann verwendet werden , so unbegrenzt zu konstruieren x , k , das ist immer ein Widerspruch ist. Rx,k
Joe Bebel
Eigentlich ziehe ich zurück, dass auf diese Weise verwendet werden kann. Im Kontext der Turing-Reduktion ist dies nicht so klar. R.
Joe Bebel
3
Einige Stellen behaupten, Kolmogorovs Komplexität sei Turing-Äquivalent zum Halting-Problem, zum Beispiel Miltersens Notizen daimi.au.dk/~bromille/DC05/Kolmogorov.pdf . Wenn das stimmt, muss es eine Turing-Reduzierung geben. Übrigens ist eine Turing-Reduzierung von Kolmogorovs Komplexität auf das Halting-Problem einfach und liefert einen anderen Beweis dafür, dass das Anhalten unentscheidbar ist.
Sasho Nikolov
folgt aus den Argumenten, die im Link in der anderen Antwort angegeben sind. InTat, da die andere Reduktion (fast) trivial ist, haben wirdass H A L T T K O . HALTTKOHALTTKO