Сложность по Колмогорову. В 1960-х годах русский математик А.Н.Колмогоров поставил вопрос: «Какова внутренняя сложность описания строки двоичных символов?» Если двоичную строку рассматривать как последовательность независимых и одинаково распределенных случайных величин, то в среднем для ее описания нам понадобилось бы число битов, равное энтропии последовательности. Но что если бы двоичными символами были двоичные цифры, составляющие миллион первых знаков двоичного разложения числа p? В этом случае строка символов кажется случайной, но ее можно получить с помощью простой компьютерной программы. Поэтому если бы мы захотели переслать миллионы битов такой строки куда-нибудь в другое место, где имеется компьютер, то могли бы вместо двоичных знаков переслать программу и попросить компьютер на месте воспроизвести заново эти миллионы битов. Таким образом, сложность описания миллиона битов разложения числа p очень мала.
Исходя из такого рода соображений, А.Н.Колмогоров определил сложность двоичной строки как длину кратчайшей программы для универсального компьютера, способной генерировать эту строку. (Такое представление о сложности независимо и почти одновременно предложили Г.Чайтин и Р.Соломонофф.) Универсальный компьютер можно рассматривать как машину Тьюринга, которая может моделировать любой другой универсальный компьютер. На первый взгляд кажется, что предложенное А.Н.Колмогоровым определение сложности бесполезно, поскольку зависит от возможностей конкретного компьютера. Но это не так, поскольку любой универсальный компьютер может моделировать любой другой универсальный компьютер, то любая программа, написанная для одного компьютера, может быть конвертирована в программу для другого компьютера путем добавления в качестве префикса «программы имитации», имеющей постоянную длину. Опираясь на эту идею, можно показать, что величина сложности по существу не зависит от компьютера. Внутренняя сложность описания любого объекта не зависит от компьютера или лица, описывающего данный объект. При некоторых предположениях можно доказать, что сложность по Колмогорову есть не что иное, как шенноновская энтропия. Иначе говоря, в среднем длина кратчайшей компьютерной программы, способной воспроизвести случайный объект, равна энтропии вероятностного распределения, из которого этот объект был извлечен. Сложность по Колмогорову предлагает единый подход к проблемам сжатия данных. Кроме того, она служит основой теории статистических выводов (бритва Оккама: «Простейшее объяснение – лучшее») и тесно связана с теорией вычислимости.
ANDLL писал(а):Дык, сладкий мой, "генератор" это то же информация
jangle писал(а):Кстати, а почему ты называешь меня - "сладкий мой"?
SLIM писал(а):Я думаю ты подумал совсем не то что он хотел сказать. Википедик ты наш
FaKk2 писал(а):Ха-ха-ха-ха! Классное слово, я теперь его буду при случае обязательно использовать.
SLIM писал(а):Я думаю ты подумал совсем не то что он хотел сказать. Википедик ты наш
jangle писал(а):Во воторых, звание википедик - полный бред, к википедии никакого отношения не имею, скорее уж к Лурке, там есть мой контент
SLIM писал(а):Конечно, и звание к википедии отношение имеет такое же
jangle писал(а):ANDLL писал(а):Дык, сладкий мой, "генератор" это то же информация
Кстати, а почему ты называешь меня - "сладкий мой"?
ANDLL писал(а):Это уменьшительно-уничижительное, если ты не понял
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 38