Dowodu złożoności Kołmogorowa nie można obliczyć przy użyciu redukcji

Szukam dowodu, że złożoności Kołmogorowa nie da się obliczyć, stosując redukcję z innego problemu nieobliczalnego. Powszechnym dowodem jest formalizacja paradoksu Berry'ego, a nie redukcja, ale powinien istnieć dowód poprzez redukcję z czegoś takiego jak problem zatrzymania lub problem korespondencji z pocztą.

Możesz znaleźć dwa różne dowody w:

Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Złożoność programowa oblicza problem zatrzymania. Biuletyn EATCS 57 (1995)

W Li, Ming, Vitányi, Paul MB; Wprowadzenie do złożoności Kołmogorowa i jego zastosowań zostało przedstawione jako ćwiczenie (z podpowiedziami, jak je rozwiązać, przypisane P. Gácsowi przez W. Gasarcha w osobistym komunikacie z 13 lutego 1992 r.).

** Postanowiłem opublikować jego rozszerzoną wersję na moim blogu .

To było zabawne pytanie do przemyślenia. Jak opisano w drugiej odpowiedzi i komentarzach poniżej, występuje redukcja Turinga od problemu Haltinga do obliczania złożoności Kołmogorowa, ale w szczególności nie ma takiej redukcji wielu, przynajmniej dla jednej definicji „obliczania złożoności Kołmogorowa”.

Formalnie zdefiniujmy, o czym mówimy. Pozwolić$HALT$oznacza standardowy język baz TM, który zatrzymuje się, gdy na wejściu zostanie podany ich opis. Pozwolić$KO$ oznaczać $\{ \langle x,k \rangle \mid x \text{ has Kolmogorov complexity exactly } k \}$.

Zakładać, że $HALT \le KO$przez pewną redukcję wielu. Pozwolić$f: \{0,1\}^* \rightarrow \{0,1\}^*$oznacza funkcję obliczaną przez tę redukcję. Zastanów się nad obrazem$HALT$ pod $f$, które oznaczę $f(HALT)$.

Uwaga $f(HALT)$ składa się z ciągów formularza $\langle x,k\rangle$ gdzie $x$ ma dokładnie złożoność Kołmogorowa $k$. Twierdzę, że$k$które występują w $f(HALT)$ są nieograniczone, ponieważ istnieje tylko skończona liczba ciągów o złożoności Kołmogorowa $k$, i $f(HALT)$ jest nieskończony.

Od $HALT$ jest rekurencyjnie wyliczalny (znany również jako Turing w niektórych książkach), z tego wynika $f(HALT)$jest rekurencyjnie wyliczalny. W połączeniu z faktem, że$k$są nieograniczone, możemy wyliczyć $f(HALT)$ dopóki nie znajdziemy $\langle x,k\rangle$ z $k$tak duże, jak chcemy; tzn. istnieje TM$M$ to na wejściu $k$ wyprowadza jakiś element $\langle x,k \rangle \in f(HALT)$.

Napisz nową bazę TM $M'$ który wykonuje następujące czynności: po pierwsze, oblicz $|M'|$za pomocą twierdzenia o rekurencji Kleene'a. Pytanie$M$ z wejściem $|M'|+1$ dostać $\langle x, |M'|+1\rangle \in f(HALT)$. Wynik$x$.

Wyraźnie wynik $x$ z $M'$ jest łańcuchem o najwyżej złożoności Kołmogorowa $|M'|$ ale $\langle x, |M'|+1\rangle \in f(HALT)$ co jest sprzecznością.

Wierzę, że można również zastąpić problem „złożoności Kołmogorowa” $k$„z” co najmniej złożonością Kołmogorowa $k$„z niewielkimi zmianami.