Сравнение статистической меры информации с аддитивной мерой Хартли

Статистическая мера информации совпадает с аддитивной мерой Хартли при условии, что / = 1, а все элементы алфавита равновероятны, тогда

где 1_Х — количество информации по Хартли;

/ш — количество информации по Шеннону.

Совпадение количества информации по Шеннону и Хартли говорит о полном использовании потенциальной информационной ёмкости.

В случае неравновероятных событий количество информации по Шеннону меньше количества информации по Хартли.

Количество алгоритмической информации

Современная теория алгоритмической информации позволила дать точные количественные определения понятиям сложности и простоты.

Объем алгоритмической информации определяется длиной компьютерной программы, необходимой для генерации данных. Минимальное число битов, необходимых для хранения программы, называется количеством алгоритмической информации.

Например, бесконечный ряд натуральных чисел 1, 2, 3, … содержит очень мало алгоритмической информации: все числа ряда можно получить с помощью коротенькой компьютерной программы. Не имеет значения, сколько времени понадобится для выполнения вычислений и какой объём памяти придется использовать, важна лишь длина программы в битах. Разумеется, точное значение количества алгоритмической информации зависит от используемого языка программирования, но об этом позже.

В качестве другого примера возьмем число л, равное 3,14 159 …. Количество алгоритмической информации в нём тоже невелико: для последовательного вычисления всех его знаков можно использовать довольно короткий алгоритм, например, вычисляющий л по формуле Гаусса, формуле Чудновского (Chudnovsky).

В противоположность этому случайное число, содержащее всего миллион знаков, например 1,341 285…64, характеризуется гораздо большим количеством алгоритмической информации. Поскольку такое число нс подчиняется закону, длина самой короткой программы, необходимой для его написания, будет близка к длине самого числа:

Начать Напечатать «1,341 285…64».

Конец В программу должны быть включены все цифры, замененные многоточием. Никакая более короткая программа нс позволит рассчитать подобную последовательность цифр: её невозможно сжать, в ней нет избыточности. Самое лучшее, что можно сделать, — просто передать как она есть. Такие последовательности называются неприводимыми, или алгоритмически случайными.

Так как имеется много разных вычислительных машин и разных языков программирования, то для определенности задаются некоторой конкретной вычислительной машиной, например машиной Тьюринга.

В этом случае количество алгоритмической информации в сообщении определяется как минимальное число внутренних состояний машины Тьюринга, требующееся для его воспроизведения.