Czy niemożność obliczenia złożoności Kołmogorowa wynika z twierdzenia Lawpowa o punkcie stałym?

Wiele twierdzeń i „paradoksów” - przekątna Cantora, nierozstrzygalność nienawiści, nierozstrzygalność złożoności Kołmogorowa, niekompletność Gödela, niekompletność Chaitina, paradoks Russella itp. - wszystkie mają w zasadzie ten sam dowód po przekątnej (zauważ, że jest to bardziej specyficzne niż to, że mogą wszystko to można udowodnić za pomocą diagonalizacji; wydaje się raczej, że wszystkie te twierdzenia faktycznie wykorzystują tę samą diagonalizację; po więcej szczegółów patrz np. Janofsky lub, dla bardziej zwięzłego i mniej sformalizowanego rachunku, moja odpowiedź na to pytanie ).

W komentarzu do wyżej wymienionego pytania Sasho Nikolov wskazał, że większość z nich była szczególnymi przypadkami twierdzenia Lawpointa o punkcie stałym . Gdyby wszystkie były szczególnymi przypadkami, byłby to dobry sposób na uchwycenie powyższej idei: naprawdę byłby jeden wynik z jednym dowodem (Lawveresem), z którego wszystkie powyższe wynikały jako bezpośrednie następstwa.

Otóż z powodu niekompletności Gödela i nierozstrzygalności problemu zatrzymania i ich przyjaciół dobrze wiadomo, że wywodzą się z twierdzenia Lawpowa o punkcie stałym (patrz np. Tutaj , tutaj lub Yanofsky'ego ). Ale nie od razu widzę, jak to zrobić w przypadku nierozstrzygalności złożoności Kołmogorowa, pomimo faktu, że podstawowy dowód jest w pewnym sensie „taki sam”. Więc:

Czy nierozstrzygalność złożoności Kołmogorowa jest szybkim następstwem - nie wymagającym dodatkowej diagonalizacji - twierdzenia Lawpowa o punkcie stałym?

lo.logic computability ct.category-theory kolmogorov-complexity Joshua Grochow
źródło

Powinienem powiedzieć, że wszystkiego, co kiedykolwiek wiedziałem na ten temat, dowiedziałem się z tego postu na blogu Andreja Bauera: math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem

Sasho Nikolov

@MaxNew: Niech

będzie obliczeniowy funkcji, obliczony za pośrednictwem TM

. Niech

być następujące TM: na pustym wejściu, to zaczyna przeżywa ciągi jednego na raz, dopóki nie znajdzie

i wyjście

. Zauważ, że

dla pewnego

zależnego tylko od

. Wtedy dla dowolnego

takie, że

f

$f$

M

$M$

M_{k}

$M_k$

x

$x$

f (x) \geq | x | > k

$f(x) \geq |x| > k$

x

$x$

| M_{k} | \leq \log_{2} (k) + c

$|M_k| \leq \log_2(k) + c$

c

$c$

| M |

$|M|$

k

$k$

(jakikolwiek wystarczająco duży

zrobi), albo nie ma takiego

(w którym to przypadku

) lub

wyprowadza niektóre

takie, że

(konstrukcyjnie), ale fakt, że

wyjście

oznacza, że

, więc

k > | M_{k} |

$k > |M_k|$

k

$k$

x

$x$

f \neq C

$f \neq C$

M_{k}

$M_k$

x

$x$

f (x) \geq | x | > k

$f(x) \geq |x| > k$

M_{k}

$M_k$

x

$x$

C (x) \leq | M_{k} | < k

$C(x) \leq |M_k| < k$

f (x) \neq C (x)

$f(x) \neq C(x)$

Joshua Grochow

@NealYoung: Podobne, ale nie do końca odpowiadają na moje pytanie. Zmniejszenie problemu zatrzymania polega na tym, że HALT jest „źródłem” nieobliczalności, a następnie używa redukcji. Ale (np.) Dowód, który podałem w powyższych komentarzach, pokazuje, że można również przyjąć złożoność K jako „źródło niepoliczalności”, ale przez bardzo podobny dowód jak w przypadku HALT. Czy ten podobny dowód może być rzeczywiście taki sam w pewnym sensie technicznym? (W tym przypadku, pokazując, że wszystkie są przykładami Twierdzenia Lawvere'a, które wydają mi się silniejsze niż wiele rodzajów redukcji). Właśnie o to mi chodzi.

Joshua Grochow

@NealYoung: Tak, uogólnia twierdzenie Rogera o punkcie stałym. Ale jeśli pomyślisz to tylko jako Twierdzenie Rogera, nie zrozumiesz sedna sprawy; Chodzi o to, że Lawvere's jest wystarczająco ogólny, aby uchwycić strategię dowodu wielu różnych dowodów, poza tym w Roger. Artykuł Yonofsky'ego, do którego nawiązuje pytanie, ma być „bezkategoryczną” ekspozycją twierdzenia Lawvere'a, przyjazną dla ludzi, dla których teoria kategorii Lawvere'a może być zastraszająca.

Joshua Grochow

Zobacz także cstheory.stackexchange.com/a/2830

András Salamon

EDYCJA: Dodanie zastrzeżenia, że twierdzenie Rogera o stałym punkcie może nie być szczególnym przypadkiem Lawvere'a.

Oto dowód, który może być „bliski” ... Używa on twierdzenia Rogera o stałym punkcie zamiast twierdzenia Lawvere'a. (Patrz sekcja komentarzy poniżej, aby uzyskać dalszą dyskusję.)

Niech będzie złożonością Kołmogorowa ciągu . $K(x)$ $x$

lemat . nie jest obliczalny $K$ .

Dowód .

Załóżmy dla sprzeczności, że jest obliczalny. $K$
Zdefiniuj $K'(x)$ jako minimalną długość kodowania dowolnej maszyny Turinga z . $M$ $L(M) = \{x\}$
Istnieje stała taka, że $c$ dla wszystkich łańcuchów . $|K(x) - K'(x)|\le c$ $x$
Określić funkcję taki, że gdzie tak, że jest minimalny, tak że łańcuch $f$ $f(\langle M \rangle) = \langle M' \rangle$ $L(M') = \{x\}$ $x$ . $K(x) > |\langle M\rangle| + c$
Ponieważ jest obliczalne, podobnie jest . $K$ $f$
Przez stałoprzecinkowych twierdzenia Roger , ma stałą temperaturę, a więc istnieje Turingowi Maszyna , tak że , gdzie $f$ $M_0$ $L(M_0) = L(M_0')$ . $\langle M_0' \rangle = f(\langle M_0\rangle)$
Zgodnie z definicją linii 4 mamy tak że . $f$ $L(M_0) = \{x\}$ $K(x) > |\langle M_0\rangle| + c$
Linie 3 i 7 oznaczają . $K'(x) > |\langle M_0\rangle|$
Ale z definicji w wierszu 2, , sprzeczne z linią 8. $K'$ $K'(x) \le |\langle M_0 \rangle|$

Neal Young
źródło

O ile wiem, twierdzenie Rogera o punkcie stałym nie jest przykładem twierdzenia Lawvere'a o punkcie stałym. Jest to jednak wariant, ponieważ w efektywnym toposie brzmi on następująco: jeśli

jest przewartością wielowartościową, to

ma właściwość punktu stałego. (Twierdzenie Lawvere'a w skutecznych toposach brzmi: jeśli

jest przypuszczeniem, to

ma właściwość punktu stałego.)

f : N ⇉ A^{N}

$f : \mathbb{N} \rightrightarrows A^\mathbb{N}$

A

$A$

f : B \to A^{B}

$f : B \to A^B$

A

$A$

Andrej Bauer

Powyżej mojej grupy płac, @AndrejBauer - nie znam teorii kategorii. Próbowałem przeczytać to i twoją odpowiedź tutaj . Nadal nie rozumiem. Czy możesz mi powiedzieć, w swoim komentarzu powyżej, o twierdzeniu Rogersa, co bierzesz dla funkcji

(z typem

) i co to jest

? A może zaproponować odpowiedni samouczek?

f

$f$

f : N \vec{\to} A^{N}

$f:\mathbb{N}\overrightarrow{\rightarrow} A^{\mathbb{N}}$

A

$A$

Neal Young,

Slajdy 45 i 46 w math.andrej.com/wp-content/uploads/2007/05/syncomp-mfps23.pdf (dobrą wiadomością jest to, że teraz mam określony plan i termin pisanie obszerny referat na syntetycznym obliczalności ).

Andrej Bauer,

Czy niemożność obliczenia złożoności Kołmogorowa wynika z twierdzenia Lawpowa o punkcie stałym?

Odpowiedzi: