Können wir die Kolmogorov-Komplexität nicht ausgeben?

28

Wir wollen eine Präfix-freie Kodierung von Turing-Maschinen und eine universelle Turing-Maschine U festlegen U, die bei Eingabe ( T , x )(T,x) (kodiert als Präfix-freier Code von T,T gefolgt von xx ) alle T-T Ausgaben bei Eingabe x ausgibt x(möglicherweise) beide laufen für immer). Definiert die Kolmogorov - Komplexität von xx , K ( x )K(x) , wie die Länge des kürzesten Programm pp , so dass U ( p ) = xU(p)=x .

TxT(x)|x|xT(x)K(x)lim inf | x | T ( x ) = lim inf|x|T(x)=

Die Bedingungen sind notwendig, weil

(a) wennDann wäre es einfach, eine Zahl auszugeben, die sich trivial von K (x) unterscheidet, weil sie größer als | x | + c_U ist.T ( x ) | x | K ( x ) | x | + c UT(x)|x|K(x)|x|+cU

(b) Wenn lim inf | x | T ( x ) < Clim inf|x|T(x)<C erlaubt ist, können wir für fast alle Zahlen einfach 00 (oder eine andere Konstante) ausgeben , indem wir "zum Glück" höchstens eine davon erraten (endlich viele Zahlen), die zu 00 (zu einer anderen Konstante) auswerten und dort etwas anderes ausgeben. Wir können sogar \ limsup_ {| x | \ rightarrow \ infty} T (x) = \ infty garantieren, indem wir lim sup | x | T ( x ) = lim sup|x|T(x)=etwas wie 2 log n2logn für x = 2 ^ n ausgeben x = 2 nx=2n.

Beachten Sie auch, dass unsere Aufgabe einfach wäre, wenn wir wissen, dass T ( x )T(x) nicht surjektiv ist, aber wenig darüber bekannt ist , sodass die Antwort möglicherweise von U abhängt UU, obwohl ich dies bezweifle.

Ich weiß, dass Beziehungen im Allgemeinen viel studiert werden, aber

Hat jemand jemals eine ähnliche Frage gestellt, bei der es unser Ziel ist, einen Algorithmus anzugeben, der keine Parameter ausgibt?

Meine Motivation ist dieses Problem http://arxiv.org/abs/1302.1109 .

domotorp
quelle
5
Es hängt von Ihrer Codierung, da wie in dem Thema auf Surjektivität der genannten Sie verknüpfen, könnte es sein , dass nur Programme selbst Länge gültig sind. Um Ihre Frage nicht trivial zu machen, müssen Sie mehr Hypothesen zur Kodierung haben. K pKp
Denis
2
Zu Ihrer zweiten Frage: Ja. Mit einer ganzen Zahl bezeichne die te Turing-Maschine. Eine diagonal nicht rekursive (oder DNR) Funktion ist eine Funktion so dass für alle ganzen Zahlen , . (Das heißt, wenn auf anhält , dann kann und andernfalls willkürlich sein.) Diese wurden in letzter Zeit in der Berechenbarkeit / Berechenbarkeit ziemlich viel untersucht Zufälligkeit Gemeinschaft. Google "diagonal nicht rekursiv", um Papiere dazu zu finden. M [ M ] M f : NN M [ M ] ( M ) f ( M ) [ M ] M f ( M ) [ M ] ( M ) f ( M )M[M]Mf:NNM[M](M)f(M)[M]Mf(M)[M](M)f(M)
Joshua Grochow
1
@Denis: Ich denke du liegst falsch. Nach meiner Definition von Universal-Turing-Maschinen im ersten Absatz können alle Längen gültige Programme sein.
Domotorp
3
Vor ein paar Malen habe ich (vergeblich) über eine scheinbar einfachere Version nachgedacht: (dis) beweisen, dass für groß genug ist , für alle . x 0 K ( x ) | x | / 2 x x 0x0K(x)|x|/2xx0
Marzio De Biasi
1
@Ricky: Das ist in Ordnung, ich habe keine Einschränkungen in Bezug auf die Codierung der Turing-Maschinen, nur in Bezug auf die Programme, die Sie im ersten Absatz lesen können.
Domotorp

Antworten:

7

Die Frage kann wie folgt umformuliert werden: , und wie Denis in den Kommentaren ausführt Dies ist für einige Codierungen falsch. Hier ist eine schwächere Aussage und ein versuchter Beweis dafür, der von keinerlei Details der Kodierung abhängt. Der Einfachheit halber gehe ich von einer Binärsprache aus:lim inf | x | | T ( x ) - K ( x ) | =0liminf|x||T(x)K(x)|=0

Sei eine berechenbare Funktion, die und erfüllt. . Dann . Informell kann es keine berechenbare Funktion verhindern, dass ein Ziel um die Kolmogorov-Komplexität jeder Saite herum getroffen wird, das unbegrenzt weit wächst.T : { 0 , 1 } N 0 T ( x ) | x | lim inf | x | T ( x ) = lim inf | x | | T ( x ) - K ( x ) | < T:{0,1}N0T(x)|x|liminf|x|T(x)=liminf|x||T(x)K(x)|<

Um dies zu sehen, sei eine zufällige Bit-Zahl, dh und . Für alle solches zufälliges . Beachten Sie auch, dass es unendlich viele Werte von für die gilt. Dies folgt aus den Bedingungen, die an . Nun sei die kleinste Zeichenkette, so dass . Es ist klar, dass es eine Konstante so dass , weil undn b 0 n < 2 b K ( n ) b b n b | { T ( x ) = b } | 2 b T x n th T ( x ) = b c 1 K ( x ) > b - c 1 K ( x ) < b + c 2 Knb0n<2bK(n)bbnb|{T(x)=b}|2bTxnthT(x)=bc1K(x)>bc1 K ( n ) b n x c 2K(n)bnkann aus berechnet werden . Und es gibt eine Konstante so dass , weil auch von oben nur durch eine Konstante von mehr als ist und aus berechnet werden kann . Dann ist , und wir haben eine unendliche Anzahl von Möglichkeiten für (diejenigen mit einem Vorbild der Kardinalität von mindestens ), was eine unendliche Anzahl von Werten ergibt für sind wir also fertig.xc2K(x)<b+c2 ( n ) b x n | K ( x ) - T ( x ) | < c 1 + c 2 b 2 b xK(n)bxn|K(x)T(x)|<c1+c2b2bx

Eine Folge ist , dass für einige , unendlich oft. Man könnte also sagen, wir können nichts ausgeben, was nicht der Komplexität von Kolmogorov entspricht!c Z T ( x ) = K ( x ) + ccZT(x)=K(x)+c

Dan Brumleve
quelle
1
Schön, ich denke das sollte funktionieren. Natürlich könnte es keine Zeichenketten mit , also möchten Sie vielleicht benötigen , oder? f ( x ) = b f ( x ) bf(x)=bf(x)b
Domotorp
1
Es muss damit aus . Also, ich denke, man muss auswählen, damit oder so Strings darauf . Vermutlich sollten die Annahmen implizieren, dass es unendlich viele solcher (obwohl ich es im Moment nicht ganz sehe). (Soweit ich das beurteilen kann, wurden die Annahmen nicht auf andere Weise verwendet.)f(x)=bf(x)=bnnxb,nxb,n bb2b+12b+1bb
Emil Jeřábek unterstützt Monica
1
Ja, das ist in der Tat nötig. Aber der Beweis ist einfach durch Widerspruch - wenn es immer wenn , dann können wir durch Betrachten eines beliebigen Bereichs schließen, dass mindestens Zeichenfolgen auf abgebildet sind , also unendlich viele, was widerspricht . <2b<2bb>b0b>b0b0<bBb0<bBBb0Bb0b0b0lim inf=lim inf=
Domotorp
Worüber Denis spricht, gilt nicht für die Art und Weise, wie ich Universalität in der ersten Zeile meiner Frage definiert habe. Seine Bemerkung ist auch trivial, ich habe keine Ahnung, warum so viele Leute seinen Kommentar positiv bewertet haben. Aber leider hat auch Peters falsche Antwort so viele positive Stimmen erhalten, dass ich das Vertrauen in diese Seite verliere ...
domotorp
Es spielt keine Rolle, wie die TMs codiert sind, solange meine Kriterien für das universelle TM erfüllt sind. Deshalb ist Denis 'Kommentar falsch. Wenn es als Bemerkung zu einem anderen Modell angegeben würde, wäre es etwas anderes. Wie auch immer, anstatt darüber nachzudenken, wollen wir versuchen, Ihre Idee zu stärken ...
domotorp
3

Ich denke das folgende funktioniert. Ich werde für die Kolmogorov-Komplexität verwendenC(x)

  • Geben Sie eine Zeitgrenze (etwa eine Exponentialfunktion der Länge des Eingabeprogramms) und rufen Sie das Ergebnis . Wenn ein Programm die Zeitgrenze überschreitet, tritt in eine Endlosschleife ein.UtUtUt
  • Sei das kürzeste Programm für auf . Beachten Sie, dass C t berechenbar ist.Ct(x)xt
  • Lassen Sie T ( x ) zurückkehren C t ( x ) + 1 , es sei denn , dieser Wert ist gleichIn diesem Fall wird 0 zurückgegeben. In diesem Fall wird 1 zurückgegeben, es sei denn, ist die Ausgabe des leeren Programms.|x|x
  • Da , unterscheidet sich immer von . Die Logik im vorherigen Schritt kümmert sich um die Randfälle.C(x)Ct(x)T(x)C(x)
  • Ut fungiert als Code für alle Zeichenfolgen und hat daher eine eingeschränkte Unendlichkeit.
Peter
quelle
Ein paar Kommentare, die KC-Theorie in einer alternativen (aber äquivalenten) Interpretation besagt Folgendes: Fast alle Zeichenfolgen befinden sich bereits in ihrer optimalen Darstellung (in Bezug auf ein bestimmtes Modell), mit Ausnahme von unzähligen Zeichenfolgen, die in eine optimale Darstellung umgewandelt werden können (Minimum). wrt auf ein Berechnungsmodell gegeben (oder TM). In diesem Sinne gibt fast jedes Programm optimale Zeichenfolgendarstellungen aus, aber diese sind a priori nicht bekannt (oder berechenbar)
Nikos M.
Warum haben Sie T ( x ) | x | ?
Domotorp
@domotorp Technisch haben wir T ( x ) | x | + c wobei c die Länge des kürzesten Druckprogramms ist. Natürlich gibt es diese Konstante auch für C ( x ) (und wenn das Druckprogramm nicht sehr langsam ist, ist es dieselbe Konstante).
Peter
Aber das macht die ganze Frage interessant! Ich hätte jede Funktion anstelle von | fragen können x | zB | x | / 2 + 99 , mein einziges Ziel war es, ähnliche Lösungen wie Ihre zu eliminieren.
Domotorp
@domotrop Ich verstehe, also wollen Sie T ( x ) zwingen , nicht an C ( x ) gebunden zu sein . Das ist interessanter ...
Peter