Czy złożoność Kołmogorowa jest funkcją przypuszczającą?

Naprawmy kodowanie maszyn Turinga i uniwersalnej maszyny Turinga U, która na wejściu (T, x) wypisuje dowolne T na wejściu x (być może oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla x, K (x), jako długość najkrótszego programu, p, tak aby U (p) = x.

Czy istnieje takie N, że dla wszystkich n> N istnieje x z K (x) = n?

Uwaga. Jeśli zdefiniujemy uniwersalne maszyny Turinga w inny sposób, odpowiedź może być przecząca. Na przykład rozważmy U, które na wejściu (T, x) symuluje T na x, jeśli długość (T, x) jest podzielna przez 100, a poza tym nic nie robi. Można zmodyfikować ten przykład na kilka sposobów, aby uzyskać kontrprzykłady dla różnych definicji uniwersalnych maszyn Turinga.

cc.complexity-theory universal-computation kolmogorov-complexity universal-turing-machines domotorp
źródło

Daleko od tego, o co prosisz, ale myślę, że nie jest trudno udowodnić, że obraz

K

$K$ ma dodatnią gęstość liniową niezależnie od

U

$U$ . Oznacza to na przykład, że

K (x)

$K(x)$ jest nieskończenie często złożony.

Dan Brumleve,

Odpowiedzi:

Tylko rozszerzony komentarz bez głębokiego wglądu: być może możesz oszukać kodowanie maszyny Turinga i zbudować sztuczne kodowanie, które prowadzi do zaskakującej złożoności Kołmogorowa:

$0$ przedstawia maszynę Turinga, która wysyła $0$ (1 stan TM);
$0p$ przedstawia maszynę Turinga, która wysyła $p+1$ (liczba reprezentowana przez ciąg binarny $p$ plus jeden); jest to po prostu domniemana „spakowana” wersja rozstrzygalnej TM, która generuje dane wyjściowe $p+1$ ;
$1p$ reprezentuje $p+1$ -ta maszyna Turinga w standardowym wyliczeniu (wyliczenie może pomijać TM już dołączone $0$ i $0p$ ).

Odpowiednia uniwersalna TM na wejściu $bx$ sprawdza, jaka jest wartość $b$ , Jeśli to jest $0$ wtedy po prostu wyprowadza $x+1$ , w przeciwnym razie symuluje TM $M_{x+1}$ ( $M_0$ kiedy $x$ jest pustym ciągiem); zwróć uwagę, że $M_{x+1}$ osadza dane wejściowe.

Dla wszystkich łańcuchów $x$ , $1 \leq K(x) \leq |x|+1$ ; i dla wszystkich $n \geq 1$ tam są $2^{n}$ sznurki długości $n$ ale są tylko $2^{n-1}-1$ programy długości $< n$ które można przedstawić za pomocą $1p$ kodowanie; i tylko $2^{n}-1$ programy długości $n$ które można przedstawić za pomocą $1p$ kodowanie; więc przynajmniej ciąg $x'$ długości $n$ nie może być reprezentowany przez program $1p$ długości $\leq n$ ; ale z pewnością można to przedstawić w programie $0x'$ długości $n+1$ (nie martwimy się, jeśli istnieje również program $1p$ o tej samej długości $n+1$ to generuje).

Możemy stwierdzić, że dla wszystkich $n > 1$ istnieje łańcuch $x', |x'|=n$ takie, że $K(x') = n+1$ (więc ten konkretny K jest zaskakujący).

Marzio De Biasi
źródło