Я буду более чем благодарен, если кто-нибудь сможет объяснить мне, как колмогоровская сложность связана со случайностью и случайными входными данными.
Еще одна вещь, которую я не могу понять, - мы знаем, что вычисление колмогоровской сложности для заданного входа X неразрешимо. Учитывая это, как это может быть мерой случайности?
спасибо
Случайность по Колмогорову — это конкретное определение неопределенного интуитивного понятия «случайность» — какое другое определение вы имеете в виду, когда спрашиваете об отношении (для справки http://en.wikipedia.org/wiki/Random_number)?
Я не следую вашему мысленному образцу, когда спрашиваю, почему нужно уметь определять в общем случае, какие строки являются случайными по Колмогорову, чтобы концепция была четко определена. Не могли бы вы уточнить, что вас беспокоит? Если ничего другого, позвольте мне указать вам на проблему остановки - безусловно, концепция остановки программы четко определена, хотя в общем случае не может быть алгоритма для определения того, проявляет ли конкретная программа это свойство.
Вы должны думать наоборот. Если что-то не случайно, значит, оно следует какому-то закону, и этот закон может дать более простое описание информации. Подумайте о zip: вместо файла вы даете процедуру для создания файла, который обычно более компактен, чем исходный файл. Это возможно, потому что исходный файл содержал некоторый порядок: если бы исходный файл представлял собой случайную последовательность символов, сжатие было бы невозможно.
Если вас интересует эта тема, я настоятельно рекомендую "Вычислимость и Случайность» Андре Ниса, Oxford Logic Guides n.51.
