Определение количества информации по Колмогорову - Методы информационного анализа материальных процессов

Рассмотрим основные идеи, лежащие в основе колмогоровского определения количества информации.

Введение колмогоровской меры имеет основной целью уточнение понятий энтропии и количества информации, во-первых, без привлечения теоретико-вероятностного подхода, во-вторых, применительно к индивидуальным объектам, а не ко множествам объектов. Кратко сформулируем идею подхода Колмогорова [12].

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

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

    - Для алгоритма определяются множества возможных исходных данных, возможных промежуточных и возможных конечных результатов. При этом для представления исходных данных, промежуточных и конечных результатов могут быть заданы соответственно входной, рабочий и выходной алфавиты. Объекты, которыми оперирует алгоритм, должны быть конструктивными. Конструктивный объект характерен тем, что он строится из конечного числа исходных элементарных объектов за конечное число шагов, т. е. он должен быть конечным и весь доступен для рассмотрения. - Правила, или инструкции, согласно которым выполняется преобразование данных, должны иметь конечную длину, причем каждое правило, должно быть сформулировано таким образом, чтобы процесс его выполнения был осуществим, строго однозначно, то есть полностью детерминирован. В частности, для выполнения правила не должна требоваться какая-либо внешняя информация. Таким образом, для реализации алгоритма нужны лишь исходные данные и набор правил. - Существенно наличие некоторого операционного устройства, способного воспринимать и выполнять инструкции алгоритма (в роли такого "устройства" может выступать человек). В процессе реализации алгоритма этому устройству может потребоваться память, на объем которой не накладывается никаких конкретных ограничений. - Следует заметить, что алгоритм не обязательно должен давать должен давать результат для каждого возможного исходного данного. Кроме случая получения результата возможны еще два исхода. Во-первых, процесс поэтапного выполнения инструкций может прекратиться, не приведя к результату. Во-вторых, процесс выполнения инструкций может оказаться состоящим из бесконечно большого числа этапов. Таким образом, в множестве в множестве возможных исходный данных целесообразно выделить область применимости алгоритма - применение алгоритма к принадлежащему этой области объекту приводит к результату за конечное число шагов [13].

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

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

Раскроем основное содержание понятия "машина Тьюринга", которая состоит из:

    - операционного устройства, которое может принимать одно из конечного множества состояний ; в выделяются начальное и конечное состояния; - бесконечной ленты, разделенной на ячейки, в каждой из которых может содержаться не более одного символа конечного алфавита ; - головки, которая способна выполнять считывание и запись символов алфавита и перемещать ленту вправо и влево на одну ячейку;

- программы, состоящей из конечного набора правил вида, где определяет характер перемещения ленты.

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

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

Пусть рассматривается некоторое исходное множество объектов, причем устанавливается взаимно-однозначное соответствие между этим множеством и множеством двоичных слов конечной длины, то есть слов вида, где есть 0 или 1 (). Установленное соответствие между множествами позволит в дальнейшем в качестве объектов без существенного ограничения общности рассматривать только двоичные слова; будет обозначать длину слова. Ясно, что конечное двоичное слово можно описать так, что это слово возможно будет восстановить по его описанию. Разные слова имеют разные описания, но одно слово может иметь бесконечно много описаний. Итак, возникает вопрос, как сравнивать между собой описания двоичного слова для того, чтобы выбрать из этих описаний самое простое.

Будем считать, что описание двоичного слова задается не в произвольной словесной форме, а в виде двоичного слова - аргумента некоторой (пока фиксированной) вычислимой функции. Пока на не накладывается никаких ограничений: она может быть определена не на всех двоичных аргументах; не для каждого двоичного слова, как может оказаться, имеется двоичный прообраз (такое слово, что ). Для некоторого двоичного слова рассмотрим множество всех двоичных слов, таких, что. Пусть

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

Недостатком данного определения сложности является произвол в выборе вычислимой функции. Избавиться от этого недостатка можно с помощью следующей теоремы: существует вычислимая функция (оптимальная), такая, что для любой другой вычислимой функции при любом выполняется неравенство

,

Где - соответствующая функции и не зависящая от константа. С учетом этой теоремы определение сложности можно скорректировать следующим образом: сложностью слова называется сложность слова по некоторой фиксированной оптимальной вычислимой функции слова. Таким образом определение сложности стало инвариантным.

Аналогичным образом строится определение относительной сложности слова при заданном слове - это минимальная длина такого двоичного слова, что пара слов содержит всю информацию, необходимую для восстановления при фиксированном оптимальном способе восстановления. Способ восстановления задается вычислимой функцией от двух аргументов. Среди всех таких функций существует оптимальная, позволяющая брать самые короткие слова, добавляемые к и дающие вместе с полное описание [14].

Назовем и обозначим величины, соответственно алгоритмической энтропией и условной алгоритмической энтропией. Алгоритмическим количеством информации в индивидуальном объекте относительно индивидуального объекта называют

.

Определение колмогоровской меры информации не требует привлечения вероятностных понятий.

Похожие статьи




Определение количества информации по Колмогорову - Методы информационного анализа материальных процессов

Предыдущая | Следующая