Ist Kolmogorov-Komplexität eine surjektive Funktion?

9

Lassen Sie uns eine Codierung von Turing-Maschinen und einer universellen Turing-Maschine U festlegen, die bei Eingabe (T, x) alle T-Ausgaben bei Eingabe x ausgibt (möglicherweise laufen beide für immer). Definieren Sie die Kolmogorov-Komplexität von x, K (x) als die Länge des kürzesten Programms p, so dass U (p) = x ist.

Gibt es ein N, so dass es für alle n> N ein x mit K (x) = n gibt?

Anmerkung. Wenn wir universelle Turingmaschinen anders definieren, kann die Antwort negativ sein. Stellen Sie sich zum Beispiel ein U vor, das bei Eingabe (T, x) T bei x simuliert, wenn die Länge von (T, x) durch 100 teilbar ist und ansonsten nichts tut. Man kann dieses Beispiel auf verschiedene Arten modifizieren, um Gegenbeispiele für verschiedene Definitionen universeller Turingmaschinen zu erhalten.

domotorp
quelle
Weit entfernt von dem, wonach Sie fragen, aber ich denke, es ist nicht schwer zu beweisen, dass das Bild von unabhängig von U eine positive lineare Dichte aufweist . Dies impliziert zum Beispiel, dass K ( x ) unendlich oft zusammengesetzt ist. KUK(x)
Dan Brumleve

Antworten:

3

Nur ein ausführlicher Kommentar ohne tiefe Einsichten: Vielleicht können Sie die Codierung einer Turing-Maschine betrügen und eine künstliche Codierung erstellen , die zu einer surjektiven Kolmogorov-Komplexität führt:

  • 00
  • 0pp+1pp+1
  • 1pp+100p

bxb0x+1Mx+1M0xMx+1

x1K(x)|x|+1n12nn2n11<n1p2n1n1pxn1pn0xn+11pn+1

n>1x,|x|=nK(x)=n+1

Marzio De Biasi
quelle