Физика процессов эволюции - Эбилинг В.
Скачать (прямая ссылка):
С остальными понятиями и результатами математической лингвистики читатель может познакомиться в работе Хомского (Хомский, 1962). Математическая лингвистика нашла ряд весьма интересных приложений в биологии.
Но вернемся к проблеме сложности. Среди различных реализаций функции сложности, рассмотренных Тиле (Thiele, 1974), мы находим сложность (на основе порождающих грамматик) контекстносвободных грамматик в смысле Хомского (Хомский, 1962. Исходя из решеточной модели, развитой Бёмом и Кликсом для психологических исследований по распознаванию и переработки образов, Гейсслер и Шейдерейтер предложили меру сложности слов над некоторым алфавитом. Тиле (Thiele, 1974) и Шейдерейтер (Scheidereiter, 1974) развили и усовершенствовали понятие «грамматической сложности». Для этого они воспользовались так называемой праволинейной порождающей грамматикой, задаваемой следующей упорядоченной четверкой:
G = {N,X,P,S}.
Здесь X — алфавит, играющий роль терминальных символов грамматики, N — множество нетерминальных символов, Р — множество правил и S — старт-символ (S € N). Правила считаются контекстносвободными, причем допускаются только правила вида
а —» q, где а 6 N, q 6 (X U N)*.
Речь идет о контекстносвободной грамматике в смысле математической лингвистики. По Шейдерейтеру (Scheidereiter, 1974), в качестве сложности правила, по определению, принимается длина слова, стоящего в правой части:
К (а -» q) = l(q).
В качестве сложности слова с учетом специального представления с помощью множества вспомогательных символов N принимается сумма сложностей всех правил:
JMp) = X>(*^q)- (п.46)
I €N
Наконец, грамматическая сложность определяется как минимум сложности по всем представлениям:
Кс(р)=ттК„(р). (11.47)
N
Работы Шейдерейтера (Sheidereiter, 1974) и Тиле (Thiele, 1974) не содержат каких-ли-бо утверждений относительно сложности слов, состоящих из iz-кратного повторения одного-единственного символа. Чейтин (Chaitin, 1975) предложил приписывать слову, состоящему из v одинаковых символов двоичного алфавита, например, ООО... О
(и раз), сложность log2 v. Поэтому мы, по определению, полагаем (Ebeling, Лтёпег-
Montano, 1980)
ЛГ(ст —> А| Аг ... А„) = (1 + Mod log2 v) (11.48)
при
Ai = Аг = ... -¦ А„.
При этом речь вдет об уточнении 4-й аксиомы Тиле.
С помощью грамматической сложности мы определяем грамматическую избыточность по формуле
йс=1~^§)’ *3“(РХ *<!>)• (11.49)
В качестве еще одной величины, характеризующей слово, мы определяем длину правил La(р) как число правил, использованных при построении слова. Каждое правило а —> q, за исключением стартового правила, подсчитывается столько раз,
сколько оно используется в минимальной программе. Введение длины правил,
называемой также длиной вывода или сложностью вывода, восходит к работам Гладкого и Игараши.
Мы вычислим значение введенных выше величин для некоторых полимеров (Ebeling, Jimenez-Montano, 1980); результаты представлены в табл. 11.6. Ход вычислений мы показываем на трех примерах. Для рассмотренного выше гена ДНК Е. coli мы обнаружили в качестве короткой производящей программы следующую производящую грамматику:
S -+3337GcryA3C3G6A0AC7CAGA4G4AG715CBC
2CCACAC7GTaOCT4C5C 1A2GC
(К, = 55)
(11.50)
Для простоты мы используем в качестве вспомогательного алфавита греческий алфавит и однозначные натуральные числа. Если произвести все замены в соответствии
а ---*¦ АА (К = 2), 3---Тб (Кз = 3),
С->сс (К = 2), 4 ---*¦ ТТТА (К4 = 4),
7 ---GG (К = 2), 1/1 (Ks = 2),
1
О
О
т (К = 2), 6 ---TG (К6 = 2),
о
1 --- 0С7СТТ (К, =6), 7 ---ТС (К7 = 2),
2 ---> 67а (К2 = 3).
с приведенными 12 правилами, то возникает первоначальное молекулярное слово — последовательность ДНК гена Е. coli. Таким образом, перед нами действительно производящая грамматика для слова ДНК. Сложность этой грамматики, по определению, равна сумме длин всех правил, т. е.
Kq ^ 55 +2+2+2+2+6+3+3+4+2+2+2= 85.
Для вычисления избыточности мы используем максимальное значение сложности Kg*. При этом мы рассуждаем следующим образом. Каждая произвольная последовательность длины 126 над четырехбуквенным алфавитом представима в виде последовательности 63 пар. Но поскольку существует только 16 различных пар, непременно должны быть повторения, и возникает необходимость воспользоваться вспомогательным алфавитом из 16 символов. Для такого вспомогательного алфавита мы получили бы
