Pytania otagowane jako kolmogorov-complexity

Ten 579-bitowy program w Binary Lambda Calculus ma nieznany status zatrzymania: 01001001000100010001000101100111101111001110010101000001110011101000000111001110 10010000011100111010000001110011101000000111001110100000000111000011100111110100 00101011000000000010111011100101011111000000111001011111101101011010000000100000 10000001011100000000001110010101010101010111100000011100101010110000000001110000 00000111100000000011110000000001100001010101100000001110000000110000000100000001 00000000010010111110111100000010101111110000001100000011100111110000101101101110 00110000101100010111001011111011110000001110010111111000011110011110011110101000 0010110101000011010 Oznacza to, że nie wiadomo, czy ten program się zakończy, czy nie. Aby to ustalić, musisz rozwiązać hipotezę Collatza - lub przynajmniej dla wszystkich liczb do 2 ^ 256. W tym …

32 algorithms  computability  kolmogorov-complexity 

Studiowałem coś na temat złożoności Kołmogorowa , przeczytałem kilka artykułów i książek Vitanyi i Li i wykorzystałem koncepcję znormalizowanej odległości kompresji, aby zweryfikować stilometrię autorów (określić, w jaki sposób każdy autor pisze niektóre dokumenty tekstowe i grupowe według ich podobieństwa). W takim przypadku zastosowano kompresory danych w celu przybliżenia złożoności …

22 computability  approximation  data-compression  kolmogorov-complexity 

Istnieje wiele sposobów definiowania złożoności Kołmogorowa i zwykle wszystkie te definicje są równoważne do stałej addytywnej. To znaczy, jeśli K1K1K_1 i K2K2K_2 są funkcjami złożoności Kołmogorowa (zdefiniowanymi za pomocą różnych języków lub modeli), wówczas istnieje stała ccc taka, że ​​dla każdego łańcucha xxx , |K1(x)−K2(x)|&lt;c|K1(x)−K2(x)|&lt;c|K_1(x) - K_2(x)| < c . …

20 computability  kolmogorov-complexity 

Według Wikipedii : Nieformalnie, z punktu widzenia algorytmicznej teorii informacji, zawartość informacyjna ciągu jest równoważna długości możliwie najkrótszej możliwej niezależnej reprezentacji tego ciągu. Jaka jest analogiczna nieformalna rygorystyczna definicja „użytecznych informacji”? Dlaczego „użyteczne informacje” nie są uważane za bardziej naturalne lub bardziej podstawowe pojęcie; naiwnie wydaje się, że czysto przypadkowy …

16 information-theory  terminology  kolmogorov-complexity 

Czytałem wpis Wikipedii o złożoności Kołmogorowa ( dzięki temu pytaniu ), który stwierdza: Można wykazać, że złożoność Kołmogorowa dowolnego łańcucha nie może być większa niż kilka bajtów więcej niż długość samego łańcucha. Dlaczego miałbyś kiedykolwiek potrzebować czegoś więcej niż samego łańcucha, aby to opisać?

13 kolmogorov-complexity