Czy nie możemy przedstawić złożoności Kołmogorowa?

Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga $U$ która na wejściu $(T,x)$ (zakodowana jako kod bez prefiksu $T$ a następnie $x$ ) wyprowadza dowolne $T$ na wejściu $x$ (ewentualnie 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 maszyna Turinga $T$ , która dla każdego wejścia $x$ wyprowadza liczbę całkowitą $T(x)\le |x|$to różni się od złożoności Kołmogorowa dla $x$ , tj. $T(x)\ne K(x)$ ale $\liminf_{|x|\rightarrow \infty} T(x)=\infty$ ?

Warunki są konieczne, ponieważ

(a) jeśli $T(x)\not \le |x|$, wówczas łatwo byłoby wypisać liczbę, która jest trywialnie różna od $K(x)$ ponieważ jest większa niż $|x|+c_U$ ,

(b) jeśli $\liminf_{|x|\rightarrow \infty} T(x)<C$ jest dozwolone, wówczas możemy po prostu wyprowadzić $0$ (lub inną stałą) dla prawie wszystkich liczb, „na szczęście” zgadując co najwyżej jeden (skończenie wiele liczb), które oceniają na $0$ (na inną stałą) i generują tam coś innego. Możemy nawet zagwarantować $\limsup_{|x|\rightarrow \infty} T(x)=\infty$ , wypisując coś w rodzaju $2\log n$ dla $x=2^n$ .

Zauważ też, że nasza praca byłaby łatwa, gdybyśmy wiedzieli, że $T(x)$ nie jest przesadny, ale niewiele wiadomo na ten temat, więc odpowiedź może zależeć od $U$ , choć wątpię, by tak było.

Wiem, że stosunki są badane ogólnie, ale

Czy ktoś kiedykolwiek zadał podobne pytanie, gdzie naszym celem jest podanie algorytmu, który nie wyprowadza jakiegoś parametru?

Moją motywacją jest ten problem http://arxiv.org/abs/1302.1109 .

Pytanie można sformułować inaczej, czy , i jak Denis wskazuje w komentarzach jest to fałszywe w przypadku niektórych kodowań. Oto słabsze stwierdzenie i próba jego udowodnienia, która nie zależy od żadnych szczegółów kodowania, ale dla uproszczenia założę język binarny:$\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} = 0$

Niech będzie funkcją obliczalną spełniającą i . Następnie . Nieoficjalnie, jeśli istnieje cel wokół złożoności Kołmogorowa dla każdego łańcucha, który rośnie bezgranicznie, żadna funkcja obliczeniowa nie może go uniknąć.$T:\{0,1\}^* \rightarrow \mathbb{N}$$0 \le T(x) \le \vert x \vert$$\lim \inf_{\vert x \vert \rightarrow \infty}{T(x)} = \infty$$\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} \lt \infty$

Aby to zobaczyć, niech będzie losową liczbą bitową, tj. oraz . Dla wszystkich istnieje taki losowy . Należy również zauważyć, że istnieje nieskończona liczba wartości na których , wynika to z warunkami dotyczącymi . Teraz niech będzie najmniejszym ciągiem takim, że . Oczywiście istnieje stała taka, że , ponieważ i$n$$b$$0 \le n \lt 2^b$$K(n) \ge b$$b$$n$$b$$\vert \{T(x) = b\} \vert \ge 2^b$$T$$x$$n^{\text{th}}$$T(x) = b$$c_1$$K(x) \gt b - c_1$$K(n) \ge b$$n$można obliczyć z . I istnieje stała taka, że , ponieważ jest również ograniczona z góry tylko o stałą większą niż , a można obliczyć z . Następnie , i mamy nieskończoną liczbę opcji dla (tych z preimage kardynalności co najmniej ), co daje nieskończoną liczbę wartości dla , więc skończymy.$x$$c_2$$K(x) \lt b + c_2$$K(n)$$b$$x$$n$$\vert K(x) - T(x) \vert \lt c_1 + c_2$$b$$2^b$$x$

Implikacją jest to, że dla niektórych , nieskończenie często. Można więc powiedzieć, że nie możemy wyjść z czegoś, co nie jest złożonością Kołmogorowa!$c \in \mathbb{Z}$$T(x) = K(x) + c$

Myślę, że następujące prace. Użyję dla złożoności Kołmogorowa$C(x)$

• Podaj ograniczenie czasowe (powiedzmy, jakąś funkcję wykładniczą długości programu wejściowego) i wywołaj wynik . Jeśli program przekroczy limit czasu, wejdzie w nieskończoną pętlę.$U$$t$$U^t$$U^t$
• Niech będzie najkrótszym programem dla on . Zauważ, że jest obliczalny.$C^t(x)$$x$$t$$C^t$
• Niech zwróci , chyba że ta wartość jest równaw takim przypadku zwróć 0. O ile nie jest wyjściem pustego programu, w takim przypadku zwróć 1.$T(x)$$C^t(x) + 1$$|x|$$x$
• Ponieważ , zawsze będzie różnić się od . Logika z poprzedniego kroku zajmuje się przypadkami krawędzi.$C(x) \leq C^t(x)$$T(x)$$C(x)$
• $U^t$ działa jak kod dla wszystkich łańcuchów, więc ma ograniczoną nieskończoność.