Ist Kolmogorov-Komplexität eine surjektive Funktion?

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.

cc.complexity-theory universal-computation kolmogorov-complexity universal-turing-machines 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

eine positive lineare Dichte aufweist . Dies impliziert zum Beispiel, dass

unendlich oft zusammengesetzt ist.

K

$K$

U

$U$

K (x)

$K(x)$

Dan Brumleve

Antworten:

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:

$0$ $0$
$0p$ $p+1$ $p$ $p+1$
$1p$ $p+1$ $0$ $0p$

$bx$ $b$ $0$ $x+1$ $M_{x+1}$ $M_0$ $x$ $M_{x+1}$

$x$ $1 \leq K(x) \leq |x|+1$ $n \geq 1$ $2^{n}$ $n$ $2^{n-1}-1$ $< n$ $1p$ $2^{n}-1$ $n$ $1p$ $x'$ $n$ $1p$ $\leq n$ $0x'$ $n+1$ $1p$ $n+1$

$n > 1$ $x', |x'|=n$ $K(x') = n+1$

Marzio De Biasi
quelle