Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений

Подождите немного. Документ загружается.

8.2. Разрешающие и запрещающие контексты 341

И, наконец, X

Z не может участвовать ни в одном сплете-

нии. Строка XBZ

может сплетаться по правилу типа 6

(XB|w, XB|Z

) |= (XBZ

, XBw), w ∈ (N ∪ T )

∗

не производя при этом ничего нового. С помощью же строки

Y создать терминальную строку невозможно.

Итак, L(γ) = L(G).

Замечание 8.1. Отметим, что пары (C

, C

) в правил ах

(p; C

, C

) из H-системы с разрешающими контекстами в до-

казательстве леммы 8.2 имеют специальный вид ({D}, ∅), где

D — некий нетерминальный символ (правило типа 7 можно

заменить на (#Y $Z

#; {Y }, ∅)). Другими словами, мы лишь

проверяем наличие одного нетерминального символа в первом

терме сплетения. На это можно смотреть как на результат о

нормальной форме для наших систем.

Замечание 8.2. Правило сплетения с ровно одним проверя-

емым символом, который как и в доказательстве леммы 8.2

должен появляться в конце строки, можно в принципе реали-

зовать следующим образом.

Как отмечалось в главе 1, рестрикционные ферменты ра-

ботают лишь на двойных цепочках. Мы расплавим раствор,

чтобы получить одинарные цепочки и добавим прай мер, со-

держащий дополнение к разрешенному символу. Этот праймер

подключится только к одинарной цепочке, содержащей на кон-

це выделенный символ. Лишь эти одинарные цепочки нужно

включить в полимеразную реакцию, приводящую к удвоению

цепочек, и тогда фермент будет воздействовать лишь на них.

Теорема 8.1. EH

(F IN, pF IN) = RE.

Доказательство. Включение EH

(F IN, pF IN) ⊆ RE следует

из тезиса Чер ча–Тьюри нга или может быть доказано непосред-

ственно. Обратное включение установлено в лемме 8.2.

В доказательстве леммы 8.2 мы не брали во внимание ра-

диус используемых правил сплетения. Заменив произвольную

грамматику G на грамматику в нормальной форме Куроды, мы

342 8. Универсальность и конечные H-системы

получим расширенную H-системы с разрешающими контекста-

ми радиуса 3. Такое значение достигается в правилах сплете-

ния типа 1 (#uY $Z#vY , где |uY | и |vY | могут равняться 3).

Этот результат можно усилить.

Лемма 8.3. R E ⊆ EH

(F IN, p[2]).

Доказательство. Возьмем грамматику G = (N, T, S, P ) ти-

па 0 в нормальной форме Куроды. Обозначим через P

множе-

ство контекстно-свободных правил из P , а через P

множество

неконтекстно-свободных правил из P .

Мы построим расширенную H-систему с разрешающими

контекстами γ = (V, T, A, R), где

V = N ∪ T ∪ {B, X , X

, Z, Z

, Z

, Y }

∪ {Y

| r ∈ P

} ∪ {Z

| r ∈ P }

∪ {Y

| α ∈ N ∪ T ∪ {B}},

A = {XBSY, ZY, XZ, Z

, Z

}

∪ {ZY

, X

αZ | α ∈ N ∪ T ∪ {B}}

∪ {Z

xY | r : C → x ∈ P

}

∪ {ZY

, Z

EF Y | r : CD → EF ∈ P

а R содержит следующие группы правил:

Имитация : 1. (#CY $Z

#x; {X}, ∅)

при r : C → x ∈ P

2. (C#DY $Z#Y

; {X}, ∅),

3. (#CY

#EF ; {X}, ∅)

при r : CD → EF ∈ P

Переброска : 4. (#αY $Z#Y

; {X}, ∅),

5. (X#$X

α#Z; {Y

}, ∅),

6. (#Y

$Z#Y ; {X

}, ∅),

7. (X

#$X#Z; {Y }, ∅)

при α ∈ N ∪ T ∪ {B}.

Завершение : 8. (XB#$#Z

; {Y }, ∅),

9. (#Y $Z

#; ∅, ∅).

8.2. Разрешающие и запрещающие контексты 343

Правила типа 1 имитируют пр авил а из P

, а правила ти-

па 2, 3 — п рав ила из P

. (Мы начинаем с XBSY , и значит,

на первом шаге будем вынуждены воспользоваться правилом

типа 1. В каждом сплетении должны участво вать аксиома и

строка, произведенная на предыдущем шаге. В результате воз-

никает строка вида XwY , где w ∈ (N ∪ T ∪ {B})

∗

, а X, Y мо-

гут заменяться их вариантами с индексами.) Рассмотрим, для

примера, строку Xw

CDY и прави ло r : CD → EF ∈ P

Получим

(Xw

C|DY, Z|Y

) |=

(Xw

, ZDY ),

(Xw

|CY

, Z

|EF Y ) |=

(Xw

EF Y, Z

Правила типов 4–7 используются для сдвигов внутри стро-

ки, а правила типов 8 и 9 — для завершения р аботы γ так

же, как и в доказательстве леммы 8.2. Таким образом, имеем

L(G) = L(γ).

Ясно, что rad(γ) = 2.

Теорема 8.1 теперь может быть переписана так:

Следствие 8. 1. RE = EH

(F IN, p[2]).

Остаются открытыми три проблемы: (1) Можно ли уси-

лить лемму 8.3 до включения R E ⊆ EH

(F IN, p[1])? Мы пред-

полагаем, что EH

(F IN, p[1]) ⊆ CF , т. е. что ответ будет от-

рицательным. (2) Можно ли заранее ограничить число аксиом,

не жертвуя при этом вычислительной полнотой? (3) Можно ли

одновременно уменьшить и количество аксиом, и радиус пра-

вил сплетения? Как показывает опыт теории дескриптивной

сложности (и как мы видели в конце разд ела 7.4), ответ на

этот вопрос, скорее всего, отрицательный, т. е. весьма вероятно,

что потребуется компромисс между двумя критериями слож-

ности — card(A) и rad(R). Заметим, что при доказательстве

леммы 8.3 радиусы изменялись. Правила из R

могут иметь

радиусы произвольной величины в зависимости от длины акси-

ом системы γ. Тем не менее, как мы увидим позже, для многих

регулируемых H-систем эти два параметра могут быть одно-

временно ограничены сверху, и границы эти довольно низки.

344 8. Универсальность и конечные H-системы

Если наше первое предположение подтвердится, и окажется

верным включение EH

(F IN, p[1]) ⊆ CF , возникнет абсолют-

но новая характеризация контекстно-свободных языков, так

как обратное включение доказывается в следующей лемме.

Лемма 8.4. CF ⊆ EH

(F IN, p[1]).

Доказательство. Рассмотрим контекстно-свободную грамма-

тику G = (N, T, S, P ) в сильной нормальн ой форме Хомского,

т. е. с правилами вида X → a, X → Y Z, где X, Y, Z ∈ N, a ∈ T ,

и добавочными ограничениями, указанными в теореме 3.2:

1) если X → Y Z из P , то Y 6= Z,

2) если X → Y Z из P , то для каждого правила X → Y

из

P выполняется Z

6= Y и Y

6= Z.

Мы построим H-систему γ = (V, T, A, R) с разрешающими

контекстами, где

V = T ∪ {X

, X

| X ∈ N} ∪ {D, E},

A = {X

| X → a ∈ P } ∪ {X

D, DX

, DX

| X ∈ N} ∪ {E},

а R состоит из следующих правил сплетения:

1) (a#Y

#b; {Y

}, {Z

}) для X → Y Z ∈ P, a, b ∈ T,

2) (a#Z

$D#X

; {Y

}, ∅) для X → Y Z ∈ P, a ∈ T,

3) (X

#D$Y

#a; ∅, {X

}) для X, Y ∈ N, a ∈ T,

4) (a#X

$D#X

; {X

}, ∅) для X ∈ N, a ∈ T,

5) (a#S

$E#; {S

}, ∅) для a ∈ T,

6) (#E$S

#a; ∅, ∅) для a ∈ T.

Основная идея конструкции заключается в том, чтобы стро-

ка X

при w ∈ T

, X ∈ N порождалась в γ тогда и только

тогда, когда X =⇒

∗

w в грамматике G. (Индексы l, r в X

, X

означают соответственно «лево» и «право».) Если X = S, то

w — элемент L(G).

Правила X → a имитируются непосредст венно с помощью

аксиом, поскольку строки X

введены в A.

Рассмотрим две строки Y

, Z

, полученные в γ. Ак -

сиомы из A, соответствующие терминальным правилам из P ,

8.2. Разрешающие и запрещающие контексты 345

имеют такой же вид, остальные же аксиомы от них отличают-

ся. Если в P есть правило X → Y Z, то в R имеется правил о

типа 1, а значит, можно выполнить сплетение

, Z

) |=

, Z

Вторая строка не может вступать в новые сплетения в γ (в тер-

мах сплетения всегда должен присутствовать либо терминаль-

ный символ, либо управляющий символ D). С первой строкой

можно поступить следующим образом:

, D|X

) |=

, DZ

|D, Y

) |=

, Y

D),

, D|X

) |=

, DX

Эти шаги возможны лишь пр и условии, что в P есть прав и-

ло X → Y Z. Следовательно, мы получаем строку X

соответствующую выводу X =⇒

∗

в G. Строки же DZ

D, DX

— аксиомы.

Таким образом, ст рока X

действительно строится в γ

тогда и только тогда, когда X =⇒

∗

z в G. Получив строку

при x ∈ L(G), мы можем применить правила 5, 6 из R:

x|S

, E|) |=

x, ES

(|E, S

|x) |=

(x, S

E).

Мы получим строку x и строки, которые могут участвовать

лишь в сплетениях того же вида, ничего при этом не произво-

дя (например, (S

x|S

, E|S

) |=

, ES

)). Правило 6 не мо-

жет быть применен о раньше правила 5 из-за символа S

, кото-

рый обязан присутствов ать в строке, сплетаемой по правилу 5.

Это и завершает доказательство равенства L(G) = L(γ).

Обратимся теперь снова к доказательству леммы 8.2. Сим-

волы, наличие которых там проверяется, — элементы множе-

ства контролирующих символов

Q = {X, X

, Y } ∪ {Y

| α ∈ N ∪ T ∪ {B}}.

Присутствие одного такого символа эквивалентн о отсут-

ствию остальных, поскольку на концах всех строк, за исключе-

346 8. Универсальность и конечные H-системы

нием терминальных, обязательно стоит пара контролирующих

символов. Таки м образом, можно рассмотреть дуальный вари-

ант расширенных H-систем с разрешающими контекстами, а

именно системы с запрещающими контекстами.

Расширенная H-система с запрещающими контекстами —

это четверка γ = (V, T, A, R), где V — алфавит, T ⊆ V (терми-

нальный алфавит), A — конечный язык над V (аксиомы), а R —

конечное множество троек (мы называем их правилами с за-

прещающими контекстами) след ующего вида: p = (r; D

, D

где r = u

— правило сплетения над V , а D

, D

—

конечные подмножества множества V

∗

Для x, y, z, w ∈ V

∗

и p ∈ R, p = (r; D

, D

) полагаем

(x, y) |=

(z, w) тогда и только тогда, когда (x, y) |=

(z, w), и

ни один элемент из D

не появляется в качестве подстроки в

x, а ни один из D

— в y. Если D

= ∅ или D

= ∅, то условий

на x соответственно y, не накладывается.

С биохимической точк и зрения разрешающие контексты

можно интерпретировать как катализаторы, благоприятствую-

щие спл етени ю по соответствующему правилу, а запрещающие

контексты — как ингибиторы (замедлители реакци и), подав-

ляющие соответствующее сплетение.

Пара σ = (V, R) называется (основной) H-схемой с прави-

лами запрещающих контекстов. Язык, порождаемый γ, опре-

деляется обычным образом:

L(γ) = σ

∗

(A) ∩ T

∗

Мы обозначаем через EH

([n], f[m]), n, m > 1 семейство

языков L(γ), порождаемых расширен ными H-системами с за-

прещающими контекстами γ = (V, T, A, R) при card(A) 6 n и

rad(R) 6 m, где rad(R) — максимальный радиус правил спле-

тения r в тройках (r; D

, D

) из R. Если число аксиом или мак-

симальный радиус не ограничивается (оставаясь при этом ко-

нечным), мы заменяем [n] или [m] на F IN.

Благодаря предыдущему обсуждению мы готовы к появле-

нию равенства EH

(F IN, f[2]) = RE, но, на самом деле, верен

более сильный результат.

8.2. Разрешающие и запрещающие контексты 347

Теорема 8.2. EH

([1], f[2]) = RE.

Доказательство этой теоремы основано на двух леммах,

первая из которых соответствует леммам 8.2 и 8.3, а вторая

доказывает для запрещающих контекстов включение, ана-

логичное предполагаемому нами (но пока не доказанному)

включению RE ⊆ EH

([1], pF IN). Ради полноты, а также из-

за впечатляющей формулировки теоремы 8.2, мы представим

центральные конструкции из доказательств этих лемм.

Лемма 8.5. R E ⊆ EH

(F IN, f[2]).

Доказательство. Возьмем грамматику G = (N, T, S, P ) типа 0

в нормальной форме Куроды. Обозначим через P

множество

контекстно-свободных правил из P , а через P

—множество

неконтекстно-свободных правил из P . Построим H-сист ему с

запрещающими контекстами γ = (V, T, A, R), где V, T, A — те

же, что и при доказательстве леммы 8.3, U = N ∪ T ∪ {B},

Имитация : 1. (#CY $Z

#x; {X

}, ∅) для r : C → x ∈ P

2. (C#DY $Z#Y

; {X

}, ∅),

3. (#CY

#EF ; {X

}, ∅)

для r : CD → EF ∈ P

Переброска : 4. (#αY $Z#Y

; {X

}, ∅),

5. (X#$X

α#Z; {Y } ∪ {Y

| β ∈ U,

β 6= α} ∪ {Y

| r ∈ P

}, ∅),

6. (#Y

$Z#Y ; {X}, ∅) при α ∈ U,

7. (X

#$X#Z; {Y

| β ∈ U} ∪ {Y

| r ∈ P

}, ∅).

Завершение : 8. (XB#$#Z

; {Y

| β ∈ U} ∪ {Y

| r ∈ P

}, ∅),

9. (#Y $Z

#; {X, B}, ∅).

Равенство L(γ) = L(G) легко проверить, повторив аргумен-

ты из доказательств лемм 8.2 и 8.3.

Лемма 8.6. EH

(F IN, f[2]) ⊆ EH

([1], f[2]).

Доказательство. Рассмотрим расширенную H-систему с

запрещающими контекстами γ = (V, T, A, R), заданную кон-

струкцией из предыдущего доказательства, с правилами вида

348 8. Универсальность и конечные H-системы

(r; D

, ∅). Заметим, что при каждом сплетении второй терм

операции — аксиома. Пусть A = {w

, w

, . . . , w

}, n > 2. По-

строим расширенную H-систему с запрещающими контекстами

= (V ∪ {c}, T, {w}, R

где w = cw

. . . cw

= {(r; D

∪ {c}, {c}) | (r; D

, ∅) ∈ R} ∪ {(#c$c#; ∅, ∅)}.

Применив правило #c$c# к двум экземплярам w, мы мо-

жем разрезать один из них после символа c, стоящего перед

аксиомой w

, получив пр и этом w

c . . . w

c. Применив к нему и

еще одному экземпляру w то же правило #c$c#, мы выделим

аксиому w

в отдельную строку.

Так как правила в R теперь имеют в качестве запрещающих

контекстов D

∪ {c}, {c}, оба терма сплетения не могут содер-

жать символ c. Его удаление равносильно выделению аксиом

γ из w с помощью правила #c$c#. Отсюда L(γ) = L(γ

Заметим, что в случае запрещающих контекстов не возник-

ло нормальной формы, как в случае разрешающих контекстов,

когда в паре (C

, C

) множество C

содержало лишь один сим-

вол, а C

было пустым. С другой стороны, в случае запреща-

ющих контекстов получен результат, неизвестный для случая

разрешающих контекстов: найденные нижние границы одно-

временно устанавливаются и на число аксиом, и на радиус.

Управление с помощью запрещающих символов, как в до-

казательстве леммы 8.5, где проверялись символы, всегда по-

являющиеся на концах первого терма сплетения, может быть

легко заменено управлением с помощью отношения старшин-

ства на множестве правил сплетения.

Более точно, упорядоченная расширенная H-система — это

структура γ = (V, T, A, R, >), где V — ал фави т, T ⊆ V (терми-

нальный алфавит), A — конечный язык над V (аксиомы), R —

конечное множество правил сплетения над V , а > — отношение

частичного порядка на R.

Для x, y, z, w ∈ V

∗

и r ∈ R мы допускаем отношение

(x, y) |=

(z, w), если только ни для каких y

, z

, w

∈ V

∗

8.2. Разрешающие и запрещающие контексты 349

∈ R , таких, что r

> r, не выполняется (x, y

) |=

, w

) или

, x) |=

, w

). (Срабатывает максимальное из всех правил

сплетения, применимых к первой строке.)

Обозначим через EH

([n], ord[m]), n, m > 1, семейство язы-

ков, порождаемых упорядоченными H-системами с не более

чем n аксиомами и радиусом, не превосходящим m.

Теорема 8.3. RE = EH

([1], ord[2]).

Доказательство. Рассмотрим H-систему с запрещающими

контекстами, заданную конструкциями из доказательства

лемм 8.5 и 8.6, т. е. систему вида γ = (V, T, {w}, R ) с rad(γ) = 2

и с правилами из R двух типов: правилом #c$c#, разреза-

ющим w на части, не содержащие символ c, и правилами,

использующими всегда в качестве вторых термов сплетений

эти части. Изменим γ следующим образом. Добав им символ

к алфавиту V , и аксиому w заменим на wcZ

. Каждое

правило с запрещающими контекстами вида

; D

, D

)

с D

∪ D

6= ∅ заменим множеством правил

r = u

r(α) = α#$Z

при α ∈ D

r(α) = Z

$α# при α ∈ D

Рассмотрим отношение >, определенное следующим образом:

r(α) > r, для всех α ∈ D

∪ D

Рассмотрим, кроме того, правило

= Z

#$Z

с r

> r для всех r = u

, соответствующих началь-

ным правилам (u

; D

, D

Упорядоченную H-систему, полученную таким образом,

обозначим через γ

. Воспользовавшись правилом #c$c#, мы

сможем, как и в доказательстве леммы 8.6, выделить из

wcZ

блоки, не содержащие символ c и строку Z

. Далее,

если в строке x фигурирует символ α ∈ D

∪ D

из некоторой

350 8. Универсальность и конечные H-системы

тройки (r; D

, D

), то для сплетения (x, y) в γ

(y ∈ V

∗

) нельзя

пользоваться правилом r, а только одним из правил r(α) ил и

(α). Применение же любого из них приведет к появлению

в обеих производимых строках неудаляемого символа Z

Поэтому ограничение по старшинству вынуждает использо-

вать правила спл етени я, учитывая уже наложенные запреты.

Следовательно, L(γ) = L(γ

Рассмотренное отношение порядка можн о интерпрети-

ровать как моделирование различия между реактивностью

ферментов, подразумевающихся под правилами сплетения: из

двух ферментов, готовых рассечь одну и ту же строку, на деле

сработает более реактивный.

8.3 Языки-мишени

Расширенные H-системы с разрешающими или запрещаю-

щими контекстами моделируют биохимическую активность

катализаторов и ингибиторов, присутствие или отсутствие

которых среди реагентов регулирует реакции in vivo или in

vitro. Уп равл ени е же сплетением с помощью языков-мишеней

моделирует другой аспект биохимии, встречающийся in vivo:

естественный отбор продуктов эволюции, который не позволя-

ет задерживаться на сцене «неподходящим» формам жизни.

В «ламаркистских» терминах можно сказать, что эволюция

имеет смысл, а мутации и рекомбинации направлены в сторону

«улучшения». Представления такого рода легко выразить в

рамках нашего подхода, если ввести в рассмотр ение языки

гипотез, которым должны принадлежать получающиеся при

сплетениях строки. Такие ограничения соответствуют услов-

ным грамматикам в теории регулируемого переписывания и

грамматическим системам с языками гипотез в теории грам-

матических систем. Так же, как и в этих разделах «кл ассиче-

ской» теории формальных языков, введение дополнительных

регулирующих механизмов увеличивает выразительную силу

соответствующих систем: мы снова сможем охарактеризовать