Колмогоровская сложность

Question

Я буду более чем благодарен, если кто-нибудь сможет объяснить мне, как сложность Колмогорова связана со случайностью и случайными входами.

Еще одна вещь, которую я не могу понять - мы знаем, что вычисление колмогоровской сложности заданного входного значения X не разрешимо. Учитывая это, как это может быть мерой случайности?

спасибо

Answer 1

Случайное Колмогорова - это конкретное определение смутного интуитивного понятия «случайный» - на какое другое определение вы ссылаетесь, когда просите о связи (для справки http://en.wikipedia.org/wiki/Random_number)?

Я не следую вашему образу мышленияв вопросе, почему нужно было бы иметь возможность определить в общем случае, какие строки являются случайными по Колмогорову, чтобы концепция была четко определена. Не могли бы вы уточнить, что доставляет вам проблемы? Если ничего больше, позвольте мне указать вамк проблеме остановки - конечно, концепция остановки программы хорошо определена, хотя не может быть никакого алгоритма для определения, в общем случае, обладает ли конкретная программа свойством.

Answer 2

Ты должен думать наоборот.Если что-то не случайно, это означает, что оно следует некоторому закону , и этот закон может дать более простое описание информации.Подумайте о zip: вместо файла вы даете процедуру для создания файла, который обычно более компактен, чем исходный файл.Это возможно, потому что исходный файл содержал некоторый порядок: если исходный файл представлял собой случайную последовательность символов, сжатие было бы невозможно.

Если вас интересует эта тема, я настоятельно рекомендую " Compubilityи случайность"Андре Ниса, Oxford Logic Guides № 51.