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

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

7.3. Итеративное сплетение 311

Хотя семейства H

(F IN, [1]) и REG кажутся очень разны-

ми (они находятся на концах бесконечной иерархии), они, од-

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

Теорема 7.5. Каждый регуля рный язык есть кодирование

языка из семейства H

(F IN, [1]).

Доказательство. Пусть язык L ∈ REG порожден регулярной

грамматикой G = (N, T, S, P ). Следовательно, все правила из

P имеют вид X → aY , X → a, при X, Y ∈ N , a ∈ T . Рассмот-

рим алфавит

V = {[X, a, Y ] | X → aY ∈ P, при X , Y ∈ N, a ∈ T }

∪ {[X, a, ∗] | X → a ∈ P, при X ∈ N, a ∈ T },

H-схему

σ = (V,{[X, a, Y ]#$#[Y, b, Z] | [X , a, Y ], [Y, b, Z] ∈ V }

∪{[X, a, Y ]#$#[Y, b, ∗] | [X, a, Y ], [Y, b, ∗] ∈ V })

и конечный язык

= {[S, a, ∗] | S → a ∈ P, a ∈ T }

∪



, a

, X

][X

, a

, X

] . . . [X

, a

, X

k+1

][X

k+1

, a

k+1

, ∗]

| k > 1, X

= S, X

→ a

i+1

∈ P, 1 6 i 6 k,

k+1

→ a

k+1

∈ P, причем нет таких 1 6 i

< i

6 k,

что [X

, a

, X

] = [X

, a

, X

] = [X

, a

, X

]



(в строке из L

символ из V может встретиться самое большее

дважды). Рассмотрим также кодирование h : V −→ T , опреде-

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

h([X, a, Y ]) = h([X, a, ∗]) = a, X, Y ∈ N, a ∈ T.

Имеет место равенство

L = h(σ

∗

)).

Действительно, каждая строка из L

соответствует выво-

ду в G. Если x, y — строки из σ

∗

), опи сывающие выводы

в G, x = x

[X, a, Y ][Y, a

, Z

и y = y

, b

, Y ][Y, b, Z]y

, то

z = x

[X, a, Y ][Y, b, Z]y

∈ σ

(x, y), и, очевидно, z также соот-

312 7. Системы сплетения

ветствует выводу в G. Кодирование h сопоставляет подобной

строке w, описывающей вывод в G, строку h(w), порождаемую

как раз этим выводом. Следовательно, h(σ

∗

)) ⊆ L.

Обратно, рассмотрим строки V

∗

, описывающие выводы в G.

Такие строки w, длины меньшей или равной двум, л ежат в L

значит, и в σ

∗

). Предположим, что все такие строки, длины

меньшей или равной n (n > 2), содержатся в σ

∗

). Рассмот-

рим строку w, самую короткую среди строк длины, большей n,

для которых может быть найден вывод в G. Если w ∈ L

, то,

очевидно, w ∈ σ

∗

). Если w /∈ L

, то в трех разных местах w

встречается один и тот же символ [X, a, Y ]:

w = w

[X, a, Y ]w

Тогда

= w

[X, a, Y ]w

= w

[X, a, Y ]w

описывают корректные выводы в G и |w

| < |w|, |w

| < |w|,

следовательно, w

, w

∈ σ

∗

) по индукционному предполо-

жению.

Вид w

, w

и правил сплетений из σ позволяет заключить,

что w ∈ σ

, w

), следовательно, w ∈ σ

∗

Для каждого вывода в G мы находим строку w ∈ σ

∗

такую, что h(w) есть в точности строка, порожденная этим

выводом. Итак, L ⊆ h(σ

∗

)).

7.4 Выразительная сила расширенных H-систем

Теперь мы введем основную вычислительную модель, которую

и будем исследовать в данной и следующих главах. Здесь мы

рассмотрим ее в общей (неограниченной) форме.

В предыдущем разд еле мы уже имели дело с порождаю-

щим механизмом, основанным на операции сплетения: пара

(σ, L), где σ = (V, R) — H-схема, а L ⊆ V

∗

— данный язык,

определяла язык σ

∗

(L). В более явном виде можно записать

ее как тройку γ = (V, L, R), задающую язык L(γ) = σ

∗

(L).

Такая тройка называется H-системой. Заметим, что мы до-

7.4. Расширенные H-си стем ы 313

пускаем бесконечность компонент L, R, что контрастирует с

привычным определением грамматики как конечного механиз-

ма, порождающего, вообще говоря, бесконечный язык. Такая

расширенная точка зрения принимается, с одной стороны, ра-

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

па лемм 7.14, 7.15: при помощи конечного множества правил

сплетения и регулярных языков нельзя выйти за пределы регу-

лярности. Мы ищем вычислительно полные механизмы; путь к

этой цели подсказан леммой 7.16, в которой демонстрируются

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

кроется и идея возможного обобщения в определени и H-систем:

ввести терминальный алфавит (как в грамматиках Хомского и

системах Линденмаейра) и считать допустимыми только стро-

ки над этим алфавитом, полученные путем итеративного спле-

тения. Так мы приходим к понятию расширенной H-системы,

фундаментальному понятию, изучаемому в данной главе.

Расширенной H-системой называется четверка

γ = (V, T, A, R),

где V — а лфави т, T ⊆ V , A ⊆ V

∗

, и R ⊆ V

∗

, а

#, $ — специальные символы, не лежащие в V .

Будем называть V алфавитом γ, T — терминальным алфа-

витом, A — множеством аксиом, R — множеством правил спле-

тения. Таким образом, у нас есть основная H-схема σ = (V, R),

пополненная некоторым данным подмножеством из V и мно-

жеством аксиом.

Если T = V , скажем, что γ — нерасширенная H-система.

Ниже мы будем касаться таких систем лишь вскользь.

Язык, порожденный системой γ, опр едел яется равенством

L(γ) = σ

∗

(A) ∩ T

∗

где σ — основная H-схема в γ.

Для двух семейств языков F L

, F L

мы обозначаем че-

рез EH

(F L

, F L

) семейство языков L(γ), порожденных

расширенными H-системами γ = (V, T, A, R), такими, что

A ∈ F L

, R ∈ F L

. Некоторые результаты из раздела 7.3

314 7. Системы сплетения

могут быть переформулированы на языке расширенных H-

систем. Кроме того, имеет место следующее включение:

Лемма 7.18. R EG ⊆ EH

(F IN, F IN).

Доказательство. Возьмем язык L ∈ REG, L ⊆ T

∗

, порожден-

ный регулярной грамматикой G = (N, T, S, P ).

Построим H-систему

γ = (N ∪ T ∪ {Z}, T, A

∪ A

, R

∪ R

где

= {S},

= {ZaY | X → aY ∈ P, X, Y ∈ N, a ∈ T },

= {ZZa | X → a ∈ P, X ∈ N, a ∈ T },

= {#X$Z#aY | X → aY ∈ P, X, Y ∈ N, a ∈ T },

= {#X$ZZ#a | X → a ∈ P, X ∈ N, a ∈ T }.

Если в качестве первого терма в сплетении по п рави лу из

взять строку ZxX, возможно, и из A

(при x = c ∈ T и

U → cX ∈ P ), то получится строка вида ZxaY . Устранить

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

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

строки. С другой стороны, строка ZxX при |x| > 2 не может

быть использована как второй терм спл етения. Поэтому един-

ственный способ получить терминальную строку — начать с S,

произвольное число раз использовать сплетения относитель-

но правил из R

и закончить по правилу из R

. Первый терм

сплетения всегда берется из чи сла полученных в предыдущих

сплетениях, второй терм — из A

или из A

(на последнем

шаге). Это соответствует выводу в G, следовательно, имеем

L(γ) = L(G) = L.

Теорема 7.6. Имеют место соотношения из таблицы 7.3,

где на пересечении строки, отмеченной F L

, и столбца, от-

меченного F L

, стоит семейство EH

(F L

, F L

) или пара се-

мейств F L

, F L

, таких, что F L

⊂ EH

(F L

, F L

) ⊂ F L

Семейства F L

, F L

являются наилучшими возможными

границами среди рассматриваемых здесь шести семейств.

7.4. Расширенные H-си стем ы 315

F IN REG LIN CF CS RE

F IN REG RE RE RE RE RE

REG REG RE RE RE RE RE

LIN LIN, CF RE RE RE RE RE

CF CF RE RE RE RE RE

CS RE RE RE RE RE RE

RE RE RE RE RE RE RE

Таблица 7.3. Выразительная сила расширенных H-систем.

Доказательство. Ясно, что F L ⊆ EH

(F L, F IN) для всех

F L. Из леммы 7.18 имеем также REG ⊆ EH

(F IN, F L) для

всех F L. Из лемм 7.14, 7.15 и замкнутости семейств REG, CF

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

включения EH

(REG, F IN) ⊆ REG, EH

(CF, F IN) ⊆ CF .

Если в доказательстве отношения RE ⊆ S

(CS, F IN) в теоре-

ме 7.1 считать c

, c

нетерминальными символами, а V —

терминальным алфавитом, то получаем RE ⊆ EH

(CS, F IN).

Таким образом, отношения из первого столбца таблицы 7.3

установлены.

Из доказательства леммы 7.16 RE ⊆ EH

(F IN, REG).

Остается заметить, что EH

(F L

, F L

) ⊆ RE для всех се-

мейств F L

, F L

(это можно доказать напрямую или задей-

ствовать тезис Черча–Тьюринга).

Единственное семейство, не совпадающее ни с одним семей-

ством иерархии Хомского, — это EH

(LIN, F IN).

Два из отношений, сведенных в таблице 7.3, являются цен-

тральными для ДНК-вычислений, основанных на сплетении:

1. EH

(F IN, F IN) = REG,

2. EH

(F IN, REG) = RE.

При использовании конечной расширенной H-системы, т. е.

системы с конечным набором аксиом и конечным набором

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

регулярных языков. Возможности такого рода устройств оста-

ются на уровне конечных автоматов (регулярных грамматик

Хомского). Увеличение множества аксиом существенно не

316 7. Системы сплетения

поможет: требуется контекстное множество аксиом для того,

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

зовать RE. Однако расширение множества правил сплетения

лишь на шаг (с нашей точки зрения), т. е. исп ользов ание ре-

гулярного множества правил сплетения, приводит к скачку

на уровень возможностей машины Тьюринга (грамматики

Хомского типа 0). Бесконечное множество правил сп летен ия,

даже образующее регулярный язык, не представляет большого

практического интереса, так как «бесконечные компьютеры»

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

из двух: либо удовлетвориться «ДНК-компьютерами», спо-

собными вычислять лишь на уровне конечных автоматов,

либо пополнить модель новыми ингредиентами с тем, что-

бы по-прежнему работать с конечными множествами правил

сплетения, но сохранять возможности расширен ных H-систем

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

упоминалось в главе 3, не существует конечного автомата,

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

ных автоматов. Следовательно, нельзя надеяться на создание

универсальных, а значит, программируемых ДНК-компью-

теров из расширенных H-систем с конечными компонентами

(без допол нит ельно го управления операцией сплетения или

другого ингредиента, способного увеличить выразительную

силу системы). Выбор практически вын ужден: единственный

способ получить универсальные по Тьюрингу программируе-

мые ДНК-компьютеры из расширенных H-систем с конечными

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

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

операцией сплетения. Это и станет целью следующих глав.

В разделе 3.3 мы построили конечный автомат M

, универ-

сальный в классе конечных автоматов с ограниченным числом

состояний и символов. Применяя доказательство леммы 7.18

к M

, можно построить расширенную H-систему γ

, облада-

ющую подобными свойствами универсальности. Однако таким

способом мы получим систему сплетения, производящую стро-

ки вида bls(code(M), x) (используется обозначение из разде-

7.4. Расширенные H-си стем ы 317

ла 3.3). Можно улучшить этот результат и построить «частич-

но универсальную» H-систему с конечными составляющими,

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

том M, «программа» которого включена в множество акси-

ом этой универсальной системы. Для этого мы начнем не с

bls(code(M), x), как в разделе 3.3, а со строки, содержащей

еще одну копию x. Воспользовавшись bls(code(M ), x), мы про-

верим, лежит или нет x в L(M), и только в утвердительном

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

нальную строку x. Вот эта универсальная H-система, ассоции-

рованная с M

= (W, V, A

, R

где

W = V ∪ K ∪ K

∪ {B

, B, E, Z, c

, c

= {BqZ | q ∈ K

} ∪ {ZZ},

= {Bq

0,u

#Z$B

∪ {Bq

#Z$Bqα# | qα → αq

∈ P

, for q, q

∈ K

α ∈ V ∪ K ∪ {c

, c

}}

∪ {#ZZ$BqE# | q ∈ K}.

Если мы добавим к A

аксиому

= B

bls(code(M), x)Ex,

то получим расширенную H-систему γ

= (W, V, A

, R

), та-

кую, что L(γ

) = L(M). Действительно, единственный способ

получить строку из V

∗

, т. е. строку без символов из множества

K ∪ K

∪ {B

, B, E, Z, c

, c

}, состоит в том, чтобы шаг за ша-

гом моделировать в префиксе B

bls(code(M), x)E аксиомы w

выполнение с левой стороны правил из P

(это обеспечивается

тем, что во всех правилах сплетения требуется наличие B

или

B) до того момента, пока строка не будет приведена к виду

BqE для некоторого q ∈ K (фактически режим работы авто-

мата M

обеспечит, что q ∈ F

). После этого блок BqE можно

будет удалить с помощью правила сплетения #ZZ$BqE#.

318 7. Системы сплетения

Мы сформулируем этот важный (для ДНК-вычислений)

вывод в виде теоремы.

Теорема 7.7. Существуют расширенные H-системы с конеч-

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

автоматов с ограниченным числом состояний и ограничен-

ным числом входящих символов.

Заметим, что M «в ыполн яется» на «компьютере» γ

посредством «программы» w

, единственной строки (свя-

занной как с M, так и с x, и, следовательно, содержащей

в себе и «алгоритм», и «входные данные»). Эта «програм-

ма» не слишком проста, она даже не контекстно-свободно-

го типа из-за присутствия копий кода M. Однако строку

= B

bls(code(M), x)Ex можно получить сплетением более

простых строк: построить строку z = code(M), создать ее

копии (операцией «размножить»), затем создать произвольно

много строк вида X

, i > 1 (в действительности, потребует-

ся ровно n + 2 такие копии, где n = |x|). Если x = a

· · · a

∈ V , 1 6 i 6 n, рассмотрим также строки Y

, 1 6 i 6 n.

Наконец, рассмотрим строки B

, Z

Ex. Теперь несложно

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

строку w

= B

bls(code(M), x)Ex, начав с упоминавшихся

блоков. Символы X

, X

, Y

, Z

смогут проконтролиро-

вать эти операции, чтобы после их исключения строка стала

бы равной w

. Мы оставим эту задачу читателю.

Замечание 7.1. С математической точки зрения семейство

REG в равенстве EH

(F IN, REG) = RE можно заменить н а

(F IN, F IN), что дает равенство

(F IN, EH

(F IN, F IN)) = RE.

На первый взгляд, это решает упомянутую выше проблему

характеризации RE с помощью расширенных H-системы с

конечными составляющими. Однако это равенство не име-

ет биохимического смысла: семейство REG из равенства

(F IN, REG) = RE состоит из языков правил сплетения

(связанных с рестриктазами), в то время как семейство REG

7.4. Расширенные H-си стем ы 319

из EH

(F IN, F IN) = REG состоит из языков молекул ДНК.

С практической точки зрения это совершенно разные объекты.

Вернемся к равенству RE = EH

(F IN, REG) и доказа-

тельству включения RE ⊆ EH

(F IN, REG), данному в лем-

ме 7.16. Для построенной в ней H-системы γ = (V, T, L

, R)

card(L

) = card(P ) + 2 · card(N ∪ T ) + 5

(обозначения те же, что и в лемме 7.16). Возникает естествен-

ный вопрос: можно ли уменьшить количество аксиом? Ответ

довольно неожиданный: достаточно одной аксиомы. В то же

время уменьшение числа аксиом может увеличить их длину.

Мы докажем это в рамках более общего подхода.

Определим две меры сложности для расширенной H-систе-

мы γ = (V, T, A, R) с конечным множеством аксиом A:

nrax(γ) = card(A),

lmax(γ) = max{|x| | x ∈ A}.

(Это соответственно число аксиом и максимум их длин.) Для

меры µ ∈ {nrax, lmax} и языка L ∈ EH

(F IN, REG) положим

µ(L) = min{µ(γ) | L = L(γ)},

и при каждом k > 1 рассмотрим семейство

−1

(k) = {L ∈ EH

(F IN, REG) | µ(L) 6 k}.

В силу определений выполнены следующие включения:

Лемма 7.19. Для µ ∈ {nrax, lmax} имеем

−1

(1) ⊆ µ

−1

(2) ⊆ · · · ⊆ EH

(F IN, REG).

Обе эти иерархии схлопываются. (В терминах дескриптив-

ной сложности меры nrax, lmax тривиальны, см. раздел 3.1).

Включение EH

(F IN, REG) ⊆ lmax

−1

(4) получается из до-

казательства леммы 7.16. Если начать с грамматики в нормаль-

ной форме Куроды G = (N, T, S, P ), т. е. с правилами u → v,

в которых |u| 6 2, |v| 6 2, то для H-системы γ, построенной в

этом доказательстве, будет выполняться lmax(γ) = 4.

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

Теорема 7.8. lmax

−1

(1) ⊂ lmax

−1

(2) = EH

(F IN, REG).

320 7. Системы сплетения

Доказательство. Возьмем H-систему γ = (V, T, A, R) с конеч-

ным множеством аксиом A = {w

, w

, . . . , w

}. Рассмотрим но-

вые символы c

, c

, 1 6 i 6 n, связанные с этими аксиомами, и

построим H-систему

= (V ∪ {c

, c

| 1 6 i 6 n}, T, A

, R

где

= {c

a | 1 6 i 6 n, a ∈ V } ∪ {c

, c

| 1 6 i 6 n},

= R ∪

[

i=1

= {c

x#$c

#a | x ∈ Pref(w

), a ∈ V, xa ∈ Pref(w

)}

∪ {c

#$#c

, #c

, w

#}, 1 6 i 6 n.

Имеем L(γ) = L(γ

Включение ⊆ достаточно очевидно: начав с c

, мы можем

добавлять символ за символом, слева направо восстанавливая

. Получив c

, мы сможем также ввести символ c

; при на-

личии c

можно будет удалить c

, а затем и c

, и в результате

этого получить w

. После построения всех строк из A, мы смо-

жем во спол ьзоваться правилами из R, и значит, каждая строка

из L(γ) может быть порождена с помощью γ

Обратно, ни одна нежелательная строка не может быть п о-

лучена с помощью γ

. Действительно, нетерминальные симво-

лы c

, c

, 1 6 i 6 n, появляются во всех аксиомах γ

. Для

того чтобы удалить c

, мы должны воспользоваться правилом

#; мы получим строку, содержащую w

в качестве суф-

фикса. Следовательно, просто исключить c

из аксиомы c

мы

можем лишь когда w

= λ. В таком случае λ ∈ L(γ). С другой

стороны, удалить c

можно только в присутствии c

, более точ-

но, применив правило #c

. Мы получим строку w

Поэтому, если после построения строки c

x при x ∈ Pref(w

)

воспользоваться правилами из R для сплетения x, мы получим

строку c

z либо с условием z ∈ Pref(w

), либо с z /∈ Pref(w

В первом случае можно продолжить строить w

, во втором же

случае удалить символ c

невозможно в принципе. Следова-