Физика процессов эволюции - Эбилинг В.
Скачать (прямая ссылка):
монографии по современной алгебре. Однако эта проблема уводит нас в область семантики, занимающейся изучением отношений между знаком и его значением, и мы не будем вдаваться в этот круг проблем более подробно. Анализ со стороны физики ограничивается элементарными, «наивными» аспектами проблем. Прежде всего для физика важно, если это возможно, рассматривать информационное содержание как измеримую величину, соответствующую некоторому действительному числу. Затем физика интересуют свойства такой информационной меры и ее связь с информационной энтропией источника. В духе физического мышления и ради сознательного упрощения проблемы в целом мы сосредоточим свои усилия на поиске величин, измеримых или вычислимых по результатам измерений (например, последовательностей молекул), которые коррелированы с величиной, интуитивно воспринимаемой как информационное содержание. Начнем с вопроса о том, может ли мера информационного содержания быть независимой от способа кодирования и считывания информации. Довольно очевидно, что невозможно наряду с информационной емкостью найти вторую, не зависящую от нее, инвариантную относительно способа кодирования меру информации.
При поиске подходящей меры мы следуем идее Колмогорова, согласно которой информационное содержание структуры убывает с возрастанием степени ее «регулярности» и увеличивается с возрастанием степени ее «нерегулярности». Проблема состоит в том, чтобы найти меру регулярности или случайности (апериодичности) последовательности. Математическое определение случайности, или апериодичности, последовательности символов было предложено независимо в работах академика А. Н. Колмогорова из Москвы и бывшего тогда студентом Нью-Йоркского университета Чейтина в 1965 г. Аналогичная идея была высказана еще в 1960 г. Соломоновым при попытке квантификации простоты научных теорий. Соломонов, бывший тогда сотрудником американской «Zator Company», рассматривал научные наблюдения, как серию двоичных знаков. Задача теории состоит в том, чтобы объяснять имеющиеся наблюдения и предсказывать новые. Соломонов определяет теорию как алгоритм, воспроизводящий серию наблюдений. Если существуют два таких алгоритма, то предпочтение отдается более простому. Поскольку данные наблюдений совершенно нерегулярны, нет никакой программы, которая была бы короче, чем ряд данных, и, следовательно, никакая теория сформулирована быть не может.
Рассмотрим в качестве примера следующие двоичные последовательности
Р5 = 1111111111111111, р6 = 0101010101010101, р7 = 0110110011011110.
Ясно, что каждая из последовательностей Р5 и рб представима с помощью простой короткой программы:
P5 = 16 раз повторить 1,
рб = 8 раз повторить 01.
В последовательности Р7 никакой закономерности нет. По Чейтину и Колмогорову, последовательность случайна, если кратчайший алгоритм, позволяющий воспроизвести последовательность, требует для своей записи примерно такого же числа битов, какое необходимо для записи исходной последовательности. Иначе говоря, последовательность случайна, если она несжимаема, т. е. если не существует более короткого алгоритма, способного воспроизвести ее. Разумеется, любую заданную последовательность всегда можно произвести с помощью бесконечно большого числа алгоритмов. Кратчайший из них назовем минимальной программой. Каждая минимальная
программа с необходимостью случайна, как это следует из определения случайных последовательностей. Понятие сложности определяется следующим образом:
сложность последовательности = длина минимальной программы, производящей эту последовательность, в битах.
Рассмотрим в качестве примера последовательности нулей и единиц длиной 16. Существует 216 различных последовательностей такого типа, из которых три приведены выше (см. последовательности рз, Рб и Р7). Последовательность рз может быть воспроизведена программой длиной около log2 16 битов. Для воспроизводства последовательности Рб требуется программа длиной не менее 5 битов, а для последовательности р7 — программа длиной не менее 15 или 16 битов. Подавляющее большинство рассматриваемых последовательностей из общего числа их 216 обладают очень большой сложностью, близкой к 16 битам, и только немногие исключительные последовательности обладают малой сложностью (например, две последовательности, составляющие 2-15 от всех последовательностей, обладают сложностью, равной 4 битам).
Попытаемся уточнить введенное выше понятие сложности или случайности. В 1965 г. Колмогоров предложил для описания этих свойств новое понятие энтропии — так называемую алгоритмическую энтропию. Это новое понятие имеет большое значение для исследования последовательностей (слов), поскольку позволяет различать случайные последовательности от регулярных. Общая идея Колмогорова связывает сложность слова р с длиной кратчайшей программы q, позволяющей представить р в рамках некоторого алгоритма, языка и машины (автомата) F, т. е. F(q) = р. Последовательность называется случайной, если не существует более короткой программы, т. е. если i(q) > 1(р). С другой стороны, для регулярных последовательностей существует более короткое представление _F(q) = р с i(q) < Кр), причем сокращение длины отражает существующие в последовательности закономерности («регулярности»). Правда, Колмогоров использовал вместо понятия программы или алгоритма понятие частично рекурсивных функций, исходя из предположения о том, что класс алгоритмически вычислимых функций эквивалентен классу частично рекурсивных функций. Понятие функции применимо к нашей проблеме, если мы исходим из существования взаимно однозначных отображений последовательностей на натуральные числа. Если д(р) и д(q) — гёделевские числа, соответствующие р и q, то представимость р по q с помощью функции F означает, что
