Pytania otagowane jako kolmogorov-complexity

Złożoność Kołmogorowa łańcucha s jest równa długości najkrótszego programu obliczającego si zatrzymującego się. Mierzy brak struktury w strunie.

2
Czy nie możemy przedstawić złożoności Kołmogorowa?
Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga UUU która na wejściu (T,x)(T,x)(T,x) (zakodowana jako kod bez prefiksu TTT a następnie xxx ) wyprowadza dowolne TTT na wejściu xxx (ewentualnie oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla xxx , K(x)K(x)K(x) , jako długość najkrótszego programu ppp tak aby …
2
Obwody dolne granice i złożoność Kołmogorowa
Rozważ następujące uzasadnienie: Niech oznacza złożoność Kołmogorowa ciągu . Twierdzenie Chaitina o niekompletności tak mówiK(x)K(x)K(x)xxx dla jakiejkolwiek spójnej i wystarczająco silny system formalny , istnieje stała (zależnie tylko od formalnego systemu i jego języka) tak, że dla każdej struny , nie może udowodnić, że .SSSTTTxxxSSSK(x)≥TK(x)≥TK(x) \geq T Niech będzie funkcją …
3
Wykorzystanie złożoności Kołmogorowa jako wejściowego „rozmiaru”
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Zdefiniujmy teraz zbiory wszystkich danych wejściowych o złożoności Kołmogorowa , i zdefiniujmy sekwencję Tutaj jest średnią sekwencją czasu pracy dla , z wyjątkiem przypadków, gdy „rozmiar” danych wejściowych jest złożonością Kołmogorowa, a nie ich długością.n …
1
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 …
1
Porównanie złożoności teorii Kołmogorowa
Twierdzenie Chaitina o niekompletności mówi, że żadna wystarczająco silna teoria arytmetyki nie może udowodnić, że gdzie K ( s ) to złożoność Kołmogorowa ciągów s, a L jest wystarczająco dużą stałą. L jest wystarczająco duży, jeśli jest większy niż rozmiar w bitach maszyny sprawdzającej proof (PCM). PCM dla teorii T …
2
Wyniki kodowania kanałów przy użyciu złożoności Kołmogorowa
Zwykle do udowodnienia wyników kodowania kanału używana jest entropia Shannona. Nawet w przypadku wyników separacji kanałów źródłowych stosowana jest entropia shannon. Biorąc pod uwagę równoważność między Shannonem (globalnym) a Kołmogorowskim (lokalnym) pojęciem informacji, czy przeprowadzono badania nad wykorzystaniem złożoności Kołmogorowa do tych wyników (lub przynajmniej w celu zastąpienia części kodującej …
1
Używasz złożoności Kołmogorowa, aby ustalić dolne granice złożoności dowodu?
Motywacją tego pytania jest fakt, że większość ciągów n-bitowych jest nieściśliwa. Intuicyjnie możemy zaproponować przez analogię, że większość dowodów dla tautologii jest nieściśliwa dla wielkości wielomianowej. Zasadniczo, moja intuicja jest taka, że ​​niektóre dowody są z natury losowe i nie można ich skompresować. Czy istnieje dobre odniesienie do wysiłków badawczych …
3
Czy istnieje teoria odpowiadająca na „najprostszy program do rozwiązania problemu”?
Aby odpowiedzieć „jakie problemy można rozwiązać za pomocą komputera”, opracowaliśmy teorię obliczalności. Czy w przypadku problemów, które można obliczać, istnieje teoria, która pozwala odpowiedzieć na pytanie „czy program otrzymuję najprostszy”? Nie sądzę, aby złożoność obliczeniowa odpowiadała na pytanie. Myślę, że bierze pod uwagę, jak długo potrzebujemy (choć mierzone abstrakcyjnie). Nie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.