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

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

10.3. Двухуровневые распределенные H-системы 441

= N ∪ T ∪ {X, Y, B},

α = r

: A

= {ZEF Y },

= {#CY

$Z#E},

= N ∪ T ∪ {X, Y

, B}.

Использование символов Y

гарантирует правильную ими-

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

Завершающие компоненты (α = 7, 8, 9 в доказательстве тео-

ремы 10.5) остаются неизмененными.

Как и в доказательстве теоремы 10.5, можно увидеть, что

полученная система эквивалентна G. Кроме того, ее радиус

равен двум, размер — единице, а содержит она самое большее

3n + 2m + 4 компонент, где n = card(N ∪ T ∪ {B}) и m =

card(P ).

Доказательства теорем 10.4, 10 .5 и 10.6 конструктивны и

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

пределенными H-системами. Для этого нуж но начинать с уни-

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

сальности. «Программа» конкретной распределенной H-систе-

мы вводится в универсальную в множество аксиом второй ком-

поненты, вместо аксиомы XBSY . Как и в разделе 8.7, символ

S заменяется кодом моделируемой системы.

10.3 Двухуровневые распределенные H-системы

Распределенные H-системы из предыдущего раздела суще-

ственно используют взаимодействие, делающее их неэффек-

тивными с биохимической точки зрения: из одной компоненты

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

ляя при этом проверку фильтрующих условий. Перемещение

(длинных) последовательностей ДНК из одного места в другое

требует времени и может разр ушить молекулы, а проверка

фильтрующих условий при современных лабораторных техно-

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

точки зрения эффективности.

442 10. Распределенные H-системы

В модели, которую мы определяем ниже, такое взаимодей-

ствие не используется.

Двухуровневая распределенная H-система (степени n,

n > 1) — это структ ура

Γ = (V, T, (w

, A

, I

, E

), . . . , (w

, A

, I

, E

)),

где

1) V — алфавит,

2) T ⊆ V ,

3) w

∈ V

∗

, A

⊆ V

∗

, а I

, E

⊆ V

∗

при #, $ /∈ V .

4) Все множества A

, I

, E

, 1 6 i 6 n , конечны;

5) T — терминальный алфавит,

6) (w

, A

, I

, E

) — i-я компонента системы,

7) w

— активная аксиома,

8) A

— множество не столь активных (мы говорим, пассивных)

аксиом,

9) I

— множество внутренних правил сплетения, а

10) E

— множество внешних правил сплетения компоненты i,

1 6 i 6 n .

Можно представлять двухуровневую H-систему в виде

комплекса, который содержит n (активных) ДНК-последова-

тельностей z

, . . . , z

(первоначально, это w

, . . . , w

), с жестко

закрепленными на стенде левыми концами. Каждая из них

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

воначально из множеств A

, . . . , A

соответственно) и обладает

как «сильными» рестрикционными ферментами, которые мо-

гут «видеть» только активные строки, так и «слабыми»,

действующими только локально на z

и на ассоциированную

строку из пассивного множества. В результате локального

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

фиксом z

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

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

строк. Внешнее сплетение имеет приоритет над внутренним.

При его выполнении по правилу из множества E

соответ-

10.3. Двухуровневые распределенные H-системы 443

ствующая строка z

становится первым термом сплетения,

и значит, пол учается новая строка, фиксированная на стен-

де и имеющая общий префикс с z

; второй терм сплетения,

некоторая z

, j 6= i, остается после этой операц ии неизме-

ненным (можно считать, что для участия в сплетении была

произведена и послана к компоненте i копия z

Формально, эти опер аци и определяются следующим обра-

зом.

Содержимое компоненты i, 1 6 i 6 n, описывается парой

, M

), где x

∈ V

∗

— активная строка, а M

⊆ V

∗

— множе-

ство пассивных строк. Кортеж из n элементов π = [(x

, M

. . . , (x

, M

)] называется конфигура цией системы. Для данного

1 6 i 6 n и выпи санн ой конфигурации π мы определяем

µ(x

, π) = внешнее, если существуют r ∈ E

и x

, j 6= i, такие,

что (x

, x

) |=

(u, v) для некоторых u, v ∈ V

∗

µ(x

, π) = внутреннее в противном случае.

Далее, для двух конфигураций π = [(x

, M

), . . . , (x

, M

)]

и π

= [(x

, M

), . . . , (x

, M

)] мы записываем π =⇒

внеш

, если

выполняются следующие условия:

1) существует i, 1 6 i 6 n, такое, что µ(x

, π) = внешнее,

2) для каждого i, 1 6 i 6 n, с µ(x

, π) = внешнее имеем

, x

) |=

, z

) при некотором j, 1 6 j 6 n, j 6= i, r ∈ E

и z

∈ V

∗

; кроме того, M

= M

∪ {z

3) для каждого i, 1 6 i 6 n, с µ(x

, π) = внутреннее мы имеем

, M

) = (x

, M

Для двух конфигураций π и π

мы записываем π =⇒

внут

если выполняются следующие условия:

1) для всех i, 1 6 i 6 n, мы имеем µ(x

, π) = внутреннее,

2) для каждого i, 1 6 i 6 n, либо (x

, z) |=

, z

) при некото-

рых z ∈ M

, z

∈ V

∗

, r ∈ I

, и M

= M

∪ {z

}, либо

3) ни одно правило r ∈ I

не может быть применено к (x

, z)

при любом z ∈ M

и тогда (x

, M

) = (x

, M

Отношение =⇒

внеш

определяет внешнее сплетение, а отно-

шение =⇒

внут

— внутреннее. Заметим, что в обоих случаях

444 10. Распределенные H-системы

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

ненты, в которых нельзя использовать правило сплетения, не

меняют своего содержимого. Еще раз подчеркнем, что внеш-

нее сплетение имеет преимущество перед внутренним, а во всех

операциях роли первых термов играют активные строки. Пер-

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

вой активной строкой соответствующей компоненты, а вторая

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

ненты.

Мы пишем =⇒ как для =⇒

внеш

, так и для =⇒

внут

. Язык,

порожденный двухуровневой распределенной H-системой Γ,

определяется равенством

L(Γ) = {w ∈ T

∗

| [(w

, A

), . . . , (w

, A

)]

=⇒

∗

[(x

, M

), . . . , (x

, M

)] при

w = x

, x

∈ V

∗

, 2 6 i 6 n, и

⊆ V

∗

, 1 6 i 6 n}.

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

семейство языков, порожден-

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

лее, чем n компонентами, n > 1. Если на число компонент не

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

∗

Пример. Рассмотрим систему

Γ =



{a, b, C, D}, {a, b}, (w

, A

, I

, E

), (w

, A

, I

, E

)



где

= aD,

= {aD, Da},

= {b#C$#aD, b#C$D#a},

= {a#D$D#b},

= DbC,

= {bC},

= {b#C$#bC},

= ∅.

10.3. Двухуровневые распределенные H-системы 445

Вычисление в Γ осуществляется следующим образом:

[(a|D, {aD, Da}), (D|bC, {bC})]

=⇒

внеш

[(ab|C, {|aD, Da, DD}), (Db|C, {|bC})]

=⇒

внут

[(aba|D, {aD, D a, DD, C}), (D|b

C, {bC, C})]

=⇒

внеш

[(abab

|C, {|aD , Da, DD, C}), (Db

|C, {|bC, C})]

=⇒

внут

[(abab

aD, {aD, Da, DD, C}), (Db

C, {bC, C})] =⇒

∗

. . .

=⇒

внеш

[(abab

. . . ab

|C, {aD , D|a, DD, C}), (Db

|C, {b|C, C})]

=⇒

внут

[(abab

. . . ab

a, {aD, Da, DD, C, DC}), (Db

k+1

C, {bC, C})]

при некотором k > 1.

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

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

равной abab

. . . ab

C, после чего можно будет произвести тер-

минальную строку, заменив C на a. Следовательно,

L(Γ) = {abab

. . . ab

a | k > 1}.

Этот язык не является полулинейным, а значит, и контекст-

но-свободным.

В следующем варианте приведенной модели уровни имеют

более существенные различия.

Разделенная двухуровневая распределенная H-система —

это структура

Γ = (V, T, (w

, A

, I

), . . . , (w

, A

, I

), E),

где

1. V — алфавит,

2. T ⊆ V (терминальный алфа вит),

3. w

∈ V

∗

(активная аксиома),

4. A

⊆ V

∗

(пассивные аксиомы),

5. I

, 1 6 i 6 n, и E — множества правил сплетения над V .

Все множества A

, I

, E конечны. Элементы I

называются

внутренними правилами сплетения, 1 6 i 6 n, а элементы

E — внешними; (w

, A

, I

) — i-я компонента Γ, 1 6 i 6 n.

Язык, порождаемый Γ и обозначаемый через L(Γ), — это в

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

446 10. Распределенные H-системы

(V, T, (w

, A

, I

, E), . . . , (w

, A

, I

, E)). Мы обозначаем через

SLDH

, n > 1, семейство языков, порожденных разделенными

двухуровневыми H-системами степени, не больше n. Если n не

определено, мы пишем SLDH

∗

Теорема 10.7. RE = SLDH

= LDH

= SLDH

∗

= LDH

∗

для всех n > 3.

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

⊆ LDH

, n > 1,

SLDH

∗

⊆ LDH

∗

, LDH

⊆ LDH

n+1

, SLDH

⊆ SLDH

n+1

n > 1, следуют из определений, включение LDH

∗

⊆ RE оче-

видно. Следовательно, мы должны доказать только включение

RE ⊆ SLDH

Рассмотрим грамматику G = (N, T, S, P ) типа 0. Мы по-

строим разделенную двухуровневую распределенную H-систе-

му

Γ = (V, T, (w

, A

, I

), (w

, A

, I

), (w

, A

, I

), E)

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

, Z

, Y, C

, C

= SXXC

= {ZvXZ

| u → v ∈ P }

∪ {ZXXαZ

, ZαXXZ

| α ∈ N ∪ T },

= {#uXZ$Z#vXZ

| u → v ∈ P }

∪ {#αXZ$Z#XXαZ

, #XZ$Z#αXXZ

| α ∈ N ∪ T },

= C

= {C

Y },

= {C

#Y $C

#Z},

= C

= {C

Y },

= {C

#Z$C

#Y, C

#Y $C

#Z},

E = {C

#Z$X#X, X#X$C

#Z, X#Z

#X ,

10.3. Двухуровневые распределенные H-системы 447

#X$C

#Y, #XXC

Z#}

∪ {XXα#Z

X#, αXX#Z

Xα# | α ∈ N ∪ T }.

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

дующем. Мы моделируем работу G на активных строках в пер-

вых двух компонентах. Более точно, подстрока XX активной

строки первой компоненты указывает место, где происходит

моделирование — непосредственно слева от XX. Дл я этой цели

активная строка первой компоненты разрезается между двумя

вхождениями X, префикс остается в первой компоненте, а суф-

фикс сохраняется во второй. Делается это с помощью вн ешних

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

компонентах. Моделирование осуществляется путем внутрен-

него сплетения в первой компоненте. Затем, при наличии сим-

вола Z

(индекс s устанавливается для «имитации») две строки

связываются снова посредством внешнего сплетения. Подстро-

ку XX можно перемещать через один символ влево и анало-

гичным способом вп раво. Контролируют эту операции симво-

лы X

, X

(l = лево, r = право). После удаления подстроки XX,

а вместе с ней и символа C

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

быть не могут.

Исследуем подробно работу Γ. Рассмотрим конфигурацию

[(w

XXw

, M

), (C

Z, M

), (C

Z, M

)]. (∗)

Первоначально мы имеем w

= S, w

= λ, M

= A

, M

= A

. Мы должны сплести ак тивн ые строки по правилам

#Z$X#X, X#X$C

#Z из E. Получим конфигурацию:

[(w

XZ, M

= M

∪ {C

}),

, M

= M

∪ {w

XZ}), (C

Z, M

)].

Никакое внешнее сплетение невозможно, и мы выполняем

внутренние сплетения в первой и третьей компонентах. Суще-

ствует три возможности:

1) Если w

= w

u для некоторого u → v ∈ P , мы мо-

жем применить правило #uXZ$Z#vXZ

в компоненте 1 и

448 10. Распределенные H-системы

#Z$C

#Y — в компоненте 3. Тогда

[(w

vXZ

, M

= M

∪ {ZuXZ}), (C

, M

Y, M

= M

∪ {C

Z})].

Можно осуществить внешние сплетения, воспользовавшись

правилами X#Z

#X , C

#X$C

#Y . Это приведет к кон-

фигурации

[(w

vXXw

, M

000

= M

∪ {C

}),

Y, M

= M

∪ {C

}), (C

Y, M

)].

Теперь внешнее сплетение невозможно, а в первой компоненте

невозможно и внутреннее. Но мы можем выполнить внутрен-

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

[(w

vXXw

, M

000

), (C

Z, M

000

= M

∪ {C

Y }),

Z, M

= M

∪ {C

Y })].

Мы вернулись к конфигурации того же вида, что и первона-

чальная (∗).

Новые пассивные строки, произведенные во время этих опе-

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

и 2, они всегда совпадают с C

Y, C

Z и находятся в третьей

компоненте.

2) Если w

= w

α при некотором α ∈ N ∪ T , мы можем при-

менить правило #αXZ$Z#XXαZ

в компоненте 1 и правило

#Z$C

#Y в компоненте 3. Получаем:

[(w

XXαZ

, M

= M

∪ {ZαXZ}),

, M

), (C

Y, M

= M

∪ {C

Z})].

Теперь нужно осуществить внешние сплетения, воспользовав-

шись правилами XXα#Z

X# и C

#X$C

#Y . Это приве-

дет к следующему:

[(w

XXαw

, M

000

= M

∪ {C

}),

Y, M

= M

∪ {C

}), (C

Y, M

)].

10.3. Двухуровневые распределенные H-системы 449

В первой компоненте ни внешнее, ни внутреннее сплетение

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

в других компонентах. Получим такую конфигурацию

[(w

XXαw

, M

000

), (C

Z, M

000

= M

∪ {C

Y }),

Z, M

= M

∪ {C

Y })].

Мы вернулись к конфигурации типа (∗).

3) Если в конфигурации (∗) w

= αw

для некоторого α ∈

N ∪ T , можно поступить следующим образом: применив пра-

вило #XZ$Z#αXXZ

в первой компоненте и C

#Z$C

#Y в

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

[(w

αXXZ

, M

= M

∪ {ZXZ}), (C

, M

Y, M

= M

∪ {C

Z})].

Далее нужно выполнить внешние сплетения по пр ави лам

αXX#Z

Xα# , C

#X$C

#Y , что приведет к

[(w

αXXw

, M

000

= M

∪ {C

XαZ

}),

Y, M

= M

∪ {C

}), (C

Y, M

)].

В первой компоненте ни внешнее, ни внутреннее сплетение

невозможно. С помощью внутренних сплетений в других

компонентах мы получаем

[(w

αXXw

, M

000

), (C

Z, M

000

= M

∪ {C

Y }),

Z, M

= M

∪ {C

Y })].

И снова мы вернулись к конфигурации типа (∗).

В случае 1 при наличии XX моделировалось правило u →

v. В случ ае 2 XX переносится через символ влево , в случае 3 —

через символ вправо. Приведенные выше операции могут быть

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

жение XX, мы можем моделировать правила G в любом месте

слова.

Если мы имеем конфигурацию вида

[(wXXC

, M

), (C

Z, M

), (C

Z, M

)],

450 10. Распределенные H-системы

то внешнее сплетение можно осуществить, п римен ив правила

#XXC

Z#, C

#Z$X#X, и придя к следующему

[(w, M

= M

∪ {C

ZXXC

}),

, M

= M

∪ {wXZ}), (C

Z, M

)].

В первой компоненте н евозможно ни внешнее, ни внутреннее

сплетение. Если w — терминальная строка, то она допускается

языком, порождаемым Γ, если нет — она никогда не приведет

к терминальной строке.

Следовательно, имеем L(G) = L(Γ).

Неизвестно, является ли оп тимал ьным порог 3 в предыду-

щей теореме.

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

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

ленную двухуровневую распределенную H-систему. «Програм-

ма» для выполнения на таком «компьютере» вводится как ак-

тивная аксиома w

вместо SXXC

10.4 Распределенные H-системы,

изменяющиеся в о времени

Распределенная архитектура, которую мы рассмотрим в этом

разделе, имеет отношение к программируемым и развертыва-

ющимся H-системам, исследовавшимся в разделе 8.4: в разные

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

правил сплетения. Переход от одного множества правил к дру-

гому теперь будет определяться в цикле. Таким образом, но-

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

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

щих систем, так и контролируемым табличным системам Лин-

денмайера. Мы также можем интерпретировать эти системы

как аналоги кооперирующихся распределенных грамматиче-

ских систем, порядок включения компонент в которых регу-

лируется графом, имеющим форму кольца.

Имеется и биохимическая подоплека введения такой моде-

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