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

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

10.2. Взаимодействующие распр еде лен ные H-системы 431

∪ {X

Z | 1 6 i 6 n}

∪ {X

Z | 0 6 i 6 n − 1}

∪ {ZY

| 0 6 i 6 n},

= {#uY $Z#vY | u → v ∈ P }

∪ {#D

Y $Z#Y

, X#$X

#Z | 1 6 i 6 n}

∪ {#Y

2i+1

$Z#Y

, X

2i+1

#$X

#Z | 0 6 i 6 n − 1},

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

2i+1

, Y

2i+1

| 0 6 i 6 n − 1},

= {ZY

2i−1

, X

2i−1

Z | 1 6 i 6 n} ∪ {ZZ},

= {#Y

$Z#Y

2i−1

, X

#$X

2i−1

#Z | 1 6 i 6 n}

∪ {X

B#$#ZZ, #Y

$ZZ# },

= N ∪ T ∪ {B, X

, Y

} ∪ {X

, Y

| 1 6 i 6 n},

= {ZY, XZ, ZY

, ZX

= {#Y

$Z#Y, X

#$X#Z, #Y

$Z#Y

, X

#$X

#Z},

= N ∪ T ∪ {B, X

, Y

Исследуем работу Γ. В ее основе — уже знакомая нам идея

имитации и переброски. Начав со строки вида XwY (такой вид

имеет а ксиома XBSY ), первая компонента может либо смоде-

лировать в суффиксе w правило из P , использовав для этого

правила #uY $Z#vY , u → v ∈ P , либо начать ротацию стро-

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

маркерами X , Y , и значит, процесс может быть повторен. При

удалении символа D

с правого конца w (w = w

, 1 6 i 6 n)

символ Y заменяется на Y

(Xw

Y, Z|Y

) |= (Xw

, ZD

Y ).

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

из N ∪ T .)

Строки, содержащие Z, не могут быть переброшены из од-

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

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

можно. Рассмотрим, например, строку ZD

Y . Снова применяя

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

правило #D

Y $Z#Y

, мы пол учаем строки ZY

, ZD

Y . Ана-

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

Строку Xw

передать нельзя, но в первой компоненте

возможно следующее сплетение:

(X|w

, X

|Z) |= (XZ, X

)

для некоторого 1 6 j 6 n. Две эти операции можно вып олн ить

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

Строки, огран ичен ные маркерами X

, Y

с четными r, s,

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

вторую компоненту. Здесь осуществимы два сплетения, умень-

шающие на единицу каждый из индексов у X и Y . При

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

Таким образом, получаем:

, X

2j−1

|Z) |= (X

Z, X

2j−1

, Z|Y

2i−1

) |= (X

2j−1

2i−1

, ZY

Снова порядок этих двух операций не важен.

Строка с нечетными индексами концевых маркеров может

быть возвращена в первую компоненту. Эти действия могут и

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

минальных символов не существует. Строка с нулевым индек-

сом концевого маркера перейти во вторую компоненту не мо-

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

X , Y равен 0, то строка будет «потеряна»: ее нельзя ни переда-

вать, ни вводить в новые сплетения. Если оба маркера имеют

индекс 0, то строку можно передать третьей компоненте.

В третьей компоненте строка вида X

может быть пре-

вращена в одну из строк: XwY (эта строка переносится в пер-

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

правил из P или ротации строки), в строку X

или же в

строку со смешанным типом маркеров X, Y — со штрихом и

без штриха. В последнем случае, она снова оказывается «поте-

рянной».

10.2. Взаимодействующие распр еде лен ные H-системы 433

Строка вида X

может быть передана только во вторую

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

B|w

, |ZZ) |= (X

BZZ, w

, ZZ|) |= (w

, ZZY

при условии, что w = Bw

(которое гарантирует, что эта строка

имеет ту же перестановку, что и соответствующая строка, про-

изводимая G). Строка без концевых маркеров не может всту-

пать в новые сплетения. Если она терминальная, то ее можно

передать первой компоненте, а значит, это элемент L(Γ). В про-

тивном случае она «потеряна».

Итак, индексы двух маркеров X, Y должны достигнуть ну-

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

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

случае, мы должны иметь i = j. Это означает, что символ

, стертый с правого конца w, нужно одновременно ввести с

левого конца w. Таким образом, этап переброски выполняет-

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

перестановки данной строки. Следовател ьно, все выводы в G

можно имитировать в Γ, и обратно, только строки из L(G) мо-

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

ненту Γ. Таким образом, L(G) = L(Γ).

Взаимодействующие распределенные H-системы степени 1

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

нечными H-системами. Ввиду результатов главы 7, мы можем

записать

CDH

= R EG ⊂ CDH

(то, что второе включение собственное, доказано примером пе-

ред теоремой 10.4).

Вопрос, можно ли включен ие CDH

⊆ CDH

заменить

равенством, и, следовательно, может ли быть усилена до

n = 2 теорема 10.4, до сих пор открыт. Мы ожидаем, что

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

CDH

⊂ CF . Этот вопрос более интересен с математической

точки зрения, и гораздо менее — для ДНК-вычислений: по-

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

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

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

поненте. Интуитивно понятно, что малое число компонент

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

противоречит нашей цели.

Рассмотрим теперь саму проблему, которая послужила при-

чиной введения распределенных H-систем — ограничение чис-

ла правил, работающих вместе. Для взаимодействующей рас-

пределенной H-системы Γ = (V, T, (A

, R

, V

), . . . , (A

, R

, V

))

мы обозначим через deg(Γ) степень Γ (число компонент n), че-

рез rad(Γ) — максимум радиусов правил в Γ, и

size(Γ) = max{card(R

) | 1 6 i 6 n}.

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

мы сможем охаракт еризов ать семейство RE с помощью взаи-

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

мера, равного единице (конечно, это получается за счет снятия

ограничений на число компонент).

Теорема 10.5. Для каждой грамматики G = (N, T, S, P ) ти-

па 0 существует взаимодействующая распределенная H-си-

стема Γ, такая, что L(G) = L(Γ), и

deg(Γ) = 2(card(N ∪ T ) + 1) + card(P ) + 9,

size(Γ) = 1,

rad(Γ) = card(N ∪ T ) + 2.

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

смотрим новый символ B, и обозначим для удобства N ∪ T ∪

{B} = {D

, D

, . . . , D

}. Поскольку N 6= ∅, T 6= ∅, имеем

n > 3. Предположим, что правила из P пронумерованы r

. . . , r

, где m = card(P ). Мы построим взаимодействующую

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

V = N ∪ T ∪ {X, X

, X

, Y, Y

, Y

, Z, B, C, E},

терминальным алфавитом T , и с компонентами, описанными

ниже. Мы пронумеруем эти компоненты элементами α из мно-

жества

M = {1, 2, 3, 4, 5, 6, 7, 8, 9}

10.2. Взаимодействующие распр еде лен ные H-системы 435

∪ {D

, D

| 1 6 i 6 n} ∪ {r

| 1 6 i 6 m},

а именно

α = r

: A

= {XBSY, Zv

Y },

= {#u

Y $# v

Y }, для r

: u

→ v

∈ P,

= N ∪ T ∪ {X, Y, B}, где i = 1, 2, . . . , m;

α = D

: A

= {ZC

Y },

= {#D

Y $Z#C

= N ∪ T ∪ {X, Y, B}, где i = 1, 2, . . . , n;

α = 1 : A

= {ZY

= {#CY

$Z#Y

= N ∪ T ∪ {X, Y

, B, C};

α = 2 : A

= {X

CZ},

= {X#$X

C#Z},

= N ∪ T ∪ {X, Y

, B, C};

α = 3 : A

= {ZY

= {#Y

$Z#Y

= N ∪ T ∪ {X

, Y

, B, C};

α = 4 : A

= {XZ},

= {X

#$X#Z},

= N ∪ T ∪ {X

, Y

, B, C};

α = D

: A

= {X

Z},

= {XC

#$X

#Z},

= N ∪ T ∪ {X, Y

, B, C}, где i = 1, 2, . . . , n;

α = 5 : A

= {ZY },

= {#Y

$Z#Y },

= N ∪ T ∪ {X

, Y

, B};

α = 6 : A

= {XZ},

= {X#Z$X

#},

= N ∪ T ∪ {X

, Y, B};

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

α = 7 : A

= {ZE},

= {#Y $Z#E},

= T ∪ {X, Y, B};

α = 8 : A

= {ZZ},

= {#ZZ$XB#},

= T ∪ {X, E, B};

α = 9 : A

= {ZZ},

= {#E$ZZ#},

= T ∪ {E}.

Работа в Γ происходит следующим образом.

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

тение, так как прав ила из R

, α ∈ M, содержат контрольные

символы X , X

, X

, Y, Y

, Y

, Z.

Компоненты, пронумерованные α = r

, 1 6 i 6 m, исполь-

зуются для имитации правил из P . Это делается на правом кон-

це текущей строки вида XwY , при w ∈ (N ∪ T ∪ {B})

∗

(только

такие строки допускаются фильтрами этих компонент):

(Xw

Y, Z|v

Y ) |= (Xw

Y, Zu

Y ).

Строка Xw

Y имеет тот же тип (содержит подобные симво-

лы), что и входная строка Xw

Y . Побочный продукт, строка

Y , может войти в новое сплетение указанного типа, если

только u

= v

(следовательно, ничего нового произведено не

будет) или (с тем же эффектом) в сплетении типа

(Z|u

Y, Z|v

Y ) |= (Zv

Y, Zu

Y ).

Строку вида XwY , с w, состоящим только из символов из

N ∪ T ∪ {B}, можно передать в компоненту с номером α =

, 1 6 i 6 n. В ней символ D

, стоящий на правом конце w,

заменяется на C

(Xw

Y, Z|C

) |= (Xw

, ZD

Y ).

Строка ZD

Y может вступить только в сплетение вида

(Z|D

Y, Z|C

) |= (ZC

, ZD

Y ),

10.2. Взаимодействующие распр еде лен ные H-системы 437

не произведя ничего нового. Первую строку можно передать

как компоненте с индексом α = 1, так и компоненте с α = D

1 6 j 6 n. Во втором случае никакое сплетение невозможно.

Компоненты, соответствующие α = 1, 2, 3, 4, перемещают

символ C с прав ого конца строки на левый:

(XC

|CY

, Z|Y

) |= (XC

, ZCY

(X|C

, X

C|Z) |= (XZ, X

s+1

, Z|Y

) |= (X

s+1

, ZY

s+1

, X|Z) |= (X

Z, XC

s+1

В результате один символ C переносится с правого конца стро-

ки XC

t+1

, s, t > 0, на левый. Эту операцию можно по-

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

волы из N ∪T ∪{X, Y

, B, C}. «Основная строка», ограниченная

X , Y или же их штрихованными версиями, должна циркулиро-

вать по пути 1, 2, 3, 4 и обратно в 1. Строки же, получаемые

во время данных шагов и содержащие символ Z, могут участ-

вовать лишь в сплетениях, не производящих ничего нового.

В любой момент строка XC

, s, t > 0, произведенная

компонентой с α = 4, может быть передана в любую компонен-

ту с индексом α = D

, 1 6 i 6 n. Есл и i 6 s, мы получаем

(XC

s−i

, X

|Z) |= (XC

Z, X

s−i

Если s > i или t > 1, строку X

s−i

нельзя пере-

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

строки, содержащие X

и C одновременно. Дальнейшее спле-

тение в компоненте с α = D

для строк, начинающихся с X

невозможно. Поэтому мы должны иметь s = i и t = 0. Это

означает, что, заменяя символ D

на C

, мы обязаны заново

ввести его с левого конца строки.

Таким образом, изменения строки сводятся к циклической

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

из G в любом месте строки, порождаемой G (моделируемой

в Γ).

Теперь компоненты, пронумерованные α = 5, 6, заменяют

на Y и X

на X, чтобы и имитацию правил из G, и ротацию

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

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

лю.

В любой момент любая строка, содержащая только симво-

лы из T ∪ {B}, может быть передана в компоненту с индексом

α = 7, которая введет символ E. Единственное продолжени е

теперь состоит в удален ии вспомогательных символов. Важно

отметить, что мы можем удалить B только вместе с X, а зна-

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

новку, что и в G. Операции, выполняемые последними тремя

компонентами нашей системы, таковы:

(XBx|Y, Z|E) |= (XBxE, ZY ),

(|ZZ, XB|xE) |= (xE, XBZZ),

(x|E, ZZ|) |= (x, ZZE).

Заметим, что при всех этих операциях мы имеем x ∈ T

∗

. Марш-

рут следован ия строки вида XwY , возможно, с штрихованны-

ми версиями X или Y , приведен на рис. 10.1. Блок A содержит

компоненты, выполняющие имитацию правил из P , блок B —

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

а блок C — компоненты, заканчивающие процесс.

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

тить, что каждый вывод в G может быть имитирован в Γ, и

наоборот, все терминальные строки, достигающие первой ком-

поненты Γ, есть строки из L(G). Следовательно, L(G) = L(Γ).

Легко видеть, что Γ содержит m+2n+9 компонент (напом-

ним, что n = card(N ∪ T ∪ {B})), а rad(Γ) = n +1 (эта величина

достигается из-за R

при α = D

). Каждая компонента содер-

жит только одно правило сплетения, т. е. deg(Γ) = 1.

Замечание 10.2. Можно рассмотреть еще один параметр

акс(Γ) — наибольшее число аксиом в компонентах Γ. Тогда

для предыдущей конструкции акс(Γ) = 1.

Ценой увеличения количества компонент, мы также можем

ограничить и радиус получаемой системы.

10.2. Взаимодействующие распр еде лен ные H-системы 439

789



6 5



. . .

???

4321

- - -

. . .

???

. . .

???

?



Рис. 10.1. Движение строк в Γ.

Теорема 10.6. Для каждой грамматики G = (N, T, S, P ) ти-

па 0 можно построить взаимодействующую распределенную

H-систему Γ, т акую , что:

1) L(G) = L(Γ),

2) deg(Γ) 6 3(card(N ∪ T ) + 1) + 2 · card(P ) + 4,

3) размер (Γ) = 1,

4) rad(Γ) = 2.

Доказательство. Изменим конструкцию системы Γ в д оказа-

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

Во-первых, удалим те компоненты в блоке B на рис. 10.1,

которые совершают в строке перестановку, и рассмотрим сле-

дующие компоненты для всех i = 1, 2, . . . , n:

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

α = D

: A

= {ZY

= {#D

Y $Z#Y

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

α = D

: A

= {X

Z},

= {X#$X

#Z},

= N ∪ T ∪ {X, Y

, B};

α = D

: A

= {ZY },

= {#Y

$Z#Y },

= N ∪ T ∪ {X

, Y

, B};

α = 1 : A

= {XZ},

= {X

#$X#Z},

= N ∪ T ∪ {X

, Y, B}.

Теперь переброска осуществляется следующим образом:

(Xw|D

Y, Z|Y

) |= (XwY

, ZD

Y ),

(X|wY

, X

|Z) |= (XZ, X

w|Y

, Z|Y ) |= (X

wY, ZY

wY, X|Z) |= (X

Z, XD

wY ).

Во-вторых, изменим имитирующие компоненты в блоке A

из рис. 10.1. Более точно, мы начнем с грамматики G в нор-

мальной форме Куроды (с правилами вида C → x, C ∈ N,

x ∈ (N ∪ T )

∗

, |x| 6 2, и CD → EF при C, D, E, F ∈ N ), пред-

положив при этом, что правила G пронумерованы.

Для каждого правила r : C → x мы введем в Γ компоненту

α = r : A

= {Zx},

= {#CY $Z#x},

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

а для каждого правила r : CD → EF — компоненты

α = r : A

= {ZY

= {C#DY $Z#Y