Изменения

Перейти к: навигация, поиск

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

97 байт добавлено, 00:47, 5 января 2015
Нет описания правки
Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.
Можем дать следующее определение. ''Количество информации'', которое несет строка {{---}} это размер архива, полученного сжатием строки каким-то конкретным архиватором (например, [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_LZW LZW]). Это более нетривиальная задача, но мы можем придумать строку, которая явно несет в себе мало информации, но которую архиватор тем не менее не сожмет.
Еще более сильное определение. ''Количество информации'', которое несет строка {{---}} это размер архива, сжатого максимальным образом, самым лучшим архиватором. Но тогда встает вопрос, почему такой архиватор существует. На самом деле он есть, и в некотором смысле '''колмогоровская сложность''' строки {{---}} это размер наименьшей программы, которая печатает эту строку.
Анонимный участник

Навигация