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

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

8.6. Мультимножества 381

В пункте (iii) мы имеем дело с операциями над мульти-

множествами. Подразумевается, что записанное выше распро-

страняется и на случай x = y (тогда долж но выполняться

(x) > 2 и нужно вычесть 2 из M

(x)) или z = w (тогда мы

должны прибавить 2 к M

(z)). Когда понятно, о какой системе

γ идет речь, мы пишем =⇒ вместо =⇒

Проще говоря, при переходе от M

к M

в соответствии с

γ кратность двух элементов из M

, x и y, уменьшается на 1, а

кратность получающихся сл ов z и w увеличивается на 1. Крат-

ность всех остальных элементов из supp(M

) не меняется. По-

лучаемое мультимножество и есть M

Язык, порожденный расширенной µH-системой γ, состоит

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

кратность во время работы γ не меньше единицы. Формально,

мы определяем этот язык равенством:

L(γ) = {w ∈ T

∗

| w ∈ supp(M)

для некоторого M, такого, что A =⇒

∗

M}.

Расширенная H-система γ = (V, T, A, R), определенная в

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

µH-система с A(x) = ∞ для всех x ∈ A и с M (x) = ∞ для всех

мультимножеств M, чей носитель составлен из строк x, выве-

денных из A. Такие мультимножества, в которых M(x) = ∞

тогда и только тогда, когда M(x) > 0, называются ω-мульти-

множествами, а соответствующие H-системы могут быть на-

званы ωH-системами.

Семейство языков, порожденных расширенными µH-систе-

мами γ = (V, T, A, R ) с card(supp(A)) 6 n и rad(R) 6 m,

n, m > 1, обозначаются через EH

(µ[n], [m]). Если n или m

не ограничены, мы заменяем [n], [m] на F IN.

Аналогично, семейства EH

(F L

, F L

) можно записывать

как EH

(ωF L

, F L

), чтобы подчеркнуть тот факт, что мы ра-

ботаем с ω-мультимножествами.

Обратим внимание на то, что запись M(x) = ∞ для стро-

ки из supp(M ) не означает, что мы действительно располагаем

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

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

мы не считаем копии x: мы получаем их в любой момент, когда

они требуются. Для ДНК это значит, что в случае необходимо-

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

вательности, например, с помощью операции размножения.

Использование мультимножеств, т. е. подсчет числа вхо-

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

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

ляет дать очередную характеризацию семейства RE.

Мы разделим доказательство этого утверждения на

несколько лемм. В первой из них выполняется основная

часть работы — моделирование грамматики типа 0 с помощью

расширенной µH-системы.

Лемма 8.10. R E ⊆ EH

(µF IN, [5]).

Доказательство. Рассмотрим грамматику Хомского G =

(N, T, S, P ) типа 0 с правилами в P вида u → v при 1 6 |u| 6 2,

0 6 |v| 6 2, u 6= v (например, можно взять G в нормальной

форме Куроды). Предположим также, что правила в P пр о-

нумерованы. Через U обозначим множество N ∪ T и построим

расширенную µH-систему

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

где

1) V = N ∪ T ∪ {X

, X

, Y, Z

, Z

} ∪ {(r), [r] | r ∈ P },

2) мультимножество A содержит слово w

= X

Y SX

, крат-

ности A(w

) = 1 и следующие слова бесконечной кратности:

= (r)v[r] для r : u → v ∈ P,

= Z

αY Z

для α ∈ U,

= Z

Y αZ

для α ∈ U,

= Y Y.

3) Множество R содержит следующие правила сплетения:

1. δ

Y u#β

$(r)v#[r] для r : u → v ∈ P , β

, β

∈ U ∪

}, δ

, δ

∈ U ∪ {X

2. Y #u[r]$(r)#vα для r : u → v ∈ P , α ∈ U ∪ {X

8.6. Мультимножества 383

3. δ

Y α#β

αY #Z

, для α ∈ U, β

, β

∈ U ∪ {X

, δ

∈ U ∪ {X

4. δ#Y αZ

#αY β для α ∈ U, δ ∈ U ∪ {X

}, β ∈ U ∪{X

5. δαY #β

Y α#Z

для α ∈ U, β

∈ U, β

, β

∈ U ∪

}, δ ∈ U ∪ {X

6. δ#αY Z

#Y αβ для α ∈ U, δ ∈ U ∪ {X

}, β ∈ U ∪{X

7. #Y Y $X

Y #w для w ∈ {X

} ∪ T {X

} ∪ T

8. #X

Идея этой конструкции такова. Правила в группах 1 и 2

имитируют при наличии символа Y правила из P . Правила из

групп 3 и 4 переносят символ Y направо, а правила из групп 5

и 6 — налево. «Главная» аксиома — w

. Во все правила из

групп 1–6 входит слово, полученное из w

и содержащее б ла-

годаря этой аксиоме такой символ Y . Следовательно, в них

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

. В

определенный момент мы будем иметь два вхождения X

в на-

чале слова и два вхождения X

в конце слова (возможно, того

же самого). Правила из групп 1, 3 и 5 разделяют слова вида

на два слова X

, z

, каждое кратности один; в пра-

вилах из групп 2 и 4, 6 эти слова сводятся вместе, и возникает

слово вида X

. Правила из групп 7 и 8 удаляют вспомо-

гательные символы X

, X

, Y . Если остающееся слово терми-

нальное, то оно из L(G). Символы (r), [r] связаны с правилами

из P , а Z

и Z

— с операциями переноса.

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

верит, что каждый вывод в G можно смоделировать в γ, а

значит, L(G) ⊆ L(γ). (Можно провести индукцию по длине

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

детали. Кроме того, в дальнейшем обсуждени и будет неявно

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

в грамматике G операциями в γ.)

Подробно рассмотрим обратное включение. Утверждается,

что если A =⇒

∗

M и w ∈ T

∗

, M(w) > 0, то w ∈ L(G).

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

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

, w

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

. (Например, символы δ и β по п рави лам из группы 4 и 6

препятствуют сплетению w

с w

, α ∈ U.) На первом шаге мы

должны начать с w

, w

= X

Y SX

, A(w

) = 1. Теперь пред-

положим, что мы имеем слово X

Y w

кратности 1 (слово

— как раз такое). Если в начале w

стоит левая часть ка-

кого-нибудь прави ла из P , можно применить к нему правило

типа 1. Предположим, что мы находимся именно в такой ситу-

ации. Слово имеет вид X

Y uw

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

r : u → v ∈ P . Испол ьзуя аксиому (r)v[r] из A, получаем

Y u|w

, (r)v|[r]) |= (X

Y u[r], (r)vw

Ни одно из правил групп 1 и 3–8 не применимо к полу-

ченным словам. Из группы 2 можно использовать правило

Y # u[r]$(r)#vα, включающее в себя оба этих слова. Имеем

Y |u[r], (r)|vw

) |= (X

Y v w

, (r)u[r]).

Слово (r)u[r] не может участвовать в новом сплетении, по-

скольку предполагалось, что u 6= v в правиле r : u → v

из P . Кратность X

Y u[r] и (r)vw

снова сократилась

до 0 (и, значит, эти слова больше недоступны), кратность

Y v w

равна 1. Таким образом, мы перешли от

Y uw

к X

Y v w

сохранив кратность 1. Это соответствует применению правила

r : u → v из P . Более того, видно, что в каждый момент в теку-

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

и одно (возможно то же самое) слово, содержащее X

Если к X

Y αw

применить правило типа 3, получим

Y α|w

, Z

αY |Z

) |= (X

Y αZ

, Z

αY w

Ни одно из правил групп 1–3 и 5–8 к полученным словам непри-

менимо. По правилу же из группы 4 получаем

|Y αZ

, Z

|αY w

) |= (X

αY w

, Z

Y αZ

Первое из полученных слов заменило X

Y αw

, кратность

которого теперь стала равна 0 (значит, мы переставили Y с α),

второе — аксиома.

8.6. Мультимножества 385

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

пы 5 должно быть применено соответствующее правило типа 6,

а это приведет к перестановке символа Y с его левым соседом.

Итак, в каждый момент времени в нашем мультимноже-

стве либо одно слово X

Y w

, либо два X

, z

, каж-

дое кратности 1. Лишь в первом случае, если w

= λ, можно

удалить X

Y , применив правило группы 7; затем с помощью

правила группы 8 мы сможем убрать и X

. Это единственный

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

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

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

образом, мы можем только имитировать выводы из G и сво-

бодно двигать Y в слове кратности один. Отсюда L(γ) ⊆ L(G).

Заметим, что радиус γ ра вен 5, и достигается это значение в

правилах группы 1, где |δ

Y u| = 5 при |u| = 2.

Замечание 8.3. Оценим требуемое число копий для каждой

из аксиом. По построению, A(w

) = 1 (и это существенно для

правильной имитации G с помощью γ). Для всех w типа w

, w

мы определили A(w) = ∞. На самом деле, как можно

заметить, для каждого r ∈ P нам требуется столько копий w

сколько раз r используется в выводе в G. Далее, w

и w

нуж-

ны для каждой операции перемещения Y на лево или направо.

Слово w

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

работы γ. Так им образом, и здесь можно положить A(w

) = 1.

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

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

ностью, которая равн а 1. Таким образом мы не должны «за-

ниматься подсчетами», различая, скажем, кратности n и n + 1

при больших n. Достаточно различать кратности 0 и 1 и мак-

симум для двух слов; пр и этом наша система устроена так, что

это различение будет происходить автоматически. Нужно по-

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

дополнительных копий этих слов.

Учитывая этот факт, а также то, что при помощи техники

ПЦР можно «копировать» необходимые слова, мы видим, что с

этой т очк и зрения наша конструкция достаточно реалистична.

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

Лемма 8.11. EH

(µF IN, [m]) ⊆ EH

(µ[2], [m]) при всех

m > 1.

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

(V, T, A, R) с конечным supp(A). Пусть w

, w

, . . . , w

— слова

из supp(A), такие, что A(w

) < ∞, 0 6 i 6 n, а z

, . . . , z

—

слова из supp(A) с A(z

) = ∞, 0 6 i 6 m. Мы построим

расширенную µH-систему

= (V ∪ {c, d

, d

}, T, A

, R

где A

содержит слово

w = (w

A(w

)

A(w

)

. . . (w

A(w

)

кратности 1 и слово

z = d

c . . . cz

бесконечной кратности. Если n = 0, то w не строится, если

m = 0, то z = d

. Кроме того,

= R ∪ {#c$d

#, #d

$c#, c#$#d

Слово z можно использовать, чтобы отрезать каждое w

от w и z соответственно. Например, для того чтобы получить

, сплетем z с z, воспользовавшись c#$#d

для c, стоящего

слева от z

, т. е.

c . . . z

j−1

c|z

c . . . cz

, |z)

|= (d

c . . . cz

j−1

cz, z

c . . . cz

затем сплетем второе слово с z, снова применив #c$d

#, и по-

лучим

|c . . . cz

, z|) |= (z

, zcz

j+1

. . . cz

Можно произвести сколько угодно экземпляров слова z

поскольку A

(z) = ∞.

Для того, чтобы получить слова w

, 1 6 i 6 n, мы начнем с

левого конца строки w, применив #c$d

# к w и z. Получим

и zc(w

A(w

)−1

A(w

)

. . . (w

A(w

)

, оба кратности 1.

Воспользовавшись правилом #d

$c# для z и второго из толь-

ко что построенных слов, получим zcz и (w

A(w

)−1

A(w

)

8.6. Мультимножества 387

. . . (w

A(w

)

, снова оба кратности 1. Из первого слова можно

выделить аксиомы z

, 1 6 j 6 m, но это не нужно, посколь-

ку они уже появились с бесконечной кратностью. Со вторым

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

ва отрезав префикс w

. Таким путем, будет произведено ровно

A(w

) копий w

; аналогичным образом можно поступить и в от-

ношении других аксиом w

, . . . , w

, получив в точности A(w

)

копий w

, i = 2, . . . , n.

Использование нетерминальных символов c, d

и d

обес-

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

дут произведены по правилам из R

− R в произвольном числе

копий, в то время как каждая аксиома w

конечной кратно-

сти будет произведена только в A(w

) экземплярах. Если вос-

пользоваться правилом из R для слов вида x

, т. е. содержа-

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

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

ное слово, применив правила из R

− R. Мы начинаем с аксиом

γ, отделенных друг от друга символом c. Они имеют требуе-

мую кратн ость, что обусловлено строением слов w и z. В силу

этого, процесс будет соответствовать корректному сплетению

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

) = L(γ).

Лемма 8.12. EH

(µ[1], F IN) ⊆ REG.

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

(V, T, A, R) с supp(A) = {w}. Если A(w) < ∞, то L(γ), очевид-

но, — конечный язык (каждое слово в L(γ) имеет длину не

выше, чем |w| · A(w)).

Если A(w) = ∞, то

L(γ) ∈ EH

([1], F IN) ⊆ EH

(F IN, F IN) = REG.

Следовательно, EH

(µ[1], F IN) ⊆ REG.

Лемма 8.13. R EG ⊆ EH

(ω[1], [2]).

Доказательство. В лемме 7.18 было доказано, что REG ⊆

(F IN, F IN). Легко увидеть, что на самом деле REG ⊆

(F IN, [2]) (система и з доказательства леммы 7.18 имела

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

радиус равный двум). Пусть γ = (V, T, A, R) — полученная H-

система.

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

и в доказательстве леммы 8.11 (радиус п ри этом не меняется),

мы сможем собрать все аксиомы из A бесконечной кратности

в одну, w, и значит, получим REG ⊆ EH

(ω[1], [2]).

Теорема 8.8. REG = EH

(µ[1], [2]) = EH

(µ[1], F IN) ⊂

(µ[2], F IN) = EH

(µ[2], [m]) = RE для всех m > 5.

Доказательство. Для удобства читателя, напомним отноше-

ния, установленные ранее в четырех леммах:

Лемма 8.10: RE ⊆ EH

(µF IN, [5]).

Лемма 8.11: EH

(µF IN, [m]) ⊆ EH

(µ[2], [m]) для всех m > 1.

Лемма 8.12: EH

(µ[1], F IN) ⊆ REG.

Лемма 8.13: REG ⊆ EH

(ω[1], [2]).

Из определений следует

(ω[n], [m]) ⊆ EH

(µ[n], [m])

для всех n, m > 1, а также при замене [n], [m] на F IN. Таким

образом, из лемм 8.12 и 8.13 получаем

REG = EH

(µ[1], [2]) = EH

(µ[1], F IN).

Лемма 8.10 и лемма 8.11 означают

RE ⊆ EH

(µF IN, [m]) ⊆ EH

(µ[2], [m]), m > 5.

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

того, иметь

(µ[2], [m]) ⊆ RE,

для всех m > 5. Это завершает до казательство.

В разделах 8.1–8.5 мы охарактеризовали семейство RE, на-

кладывая на операц ию сплетения в расшир енных H-системах

некие ограничения. Навеяны эти ограничения были, главным

образом, теорией регулируемых переписываний. Они имеют

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

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

8.7. Результаты об универсальности 389

методов при попытке их реализации. Точнее, подобные огра-

ничения, вероятно, можно осуществить, регулируя сплетен ие

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

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

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

праймеров из замечания 8.2 и т. д.). Однако такой подход

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

ления: скорость, энергетическую эффективность, недетерми-

низм параллельных реакций. В частности, катастрофически

упадет скорость процесса. Остается надеяться, что регулиро-

вание этого процесса можно будет осуществить встр оенн ыми

биохимическими средствами. Это потребует значительного

прогресса биохимической техники.

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

ный недостаток: вероятность того, что две строки имеют крат-

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

чтобы вступить в реакцию сшивки, две строки должны быть

достаточно близки друг к другу. Как этого добиться реальным

путем и за короткий промежуток времени (не говоря уже о эф-

фективном времени) — открытая проблема. Например, можно

прочно закрепить две строки (такая техника хорошо изучена,

см., например, [149, 182, 206]), чтобы, сделав их более близки-

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

ция осуществима и эффективна для строк большой длины, —

это вопрос биоинженерии, выходящий за рамки данной книги.

8.7 Результаты об универсальности

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

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

с помощью расширенных H-систем, регулируемых

1) разрешающими контекстами,

2) запрещающими контекстами,

3) локальными или глобальными языками-мишенями,

4) отображениями годности,

5) отображениями правил next,

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

6) точечными мутациями, которые редактируют доступные в

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

7) двойным сплетением,

8) мультимножествами.

Итак, расширенные H-системы этих типов являются вычисли-

тельно полными, т. е. по своим возможностям они эквивалент-

ны машинам Тьюринга (грамматикам Хомского типа 0).

Однако таких результатов недостаточно для того, чтобы га-

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

пьютеров»), основанных на операции сплетения. Для этой цели

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

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

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

ответствующего класса при введении ее кода в универсальную

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

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

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

общему определению.

Рассмотрим алфавит T и класс расширенных H-систем H

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

текстами или с мультимножествами и т. д.). Элемент из H вида

= (V

, T, A

, R

где V

— алфавит, такой, что T ⊆ V

, A

⊆ V

∗

, и R

— множе-

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

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

в классе H, если для каждой γ ∈ H существует строка w

∈ V

∗

такая, что L(γ) = L(γ

), а γ

= (V

, T, A

∪ {w

}, R

Другими словами, w

, или код γ, — это «программа», вы-

полняя которую γ

имитирует действи я γ. Набор аксиомы A

можно тр актов ать как «операционную систему» нашего «ком-

пьютера» γ

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

нального алфавита, можно снять, кодируя T элементами фик-

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

символов a, b. Обозначая это код иро вани е через h, h : T

∗

−→

{a, b}

∗

, мы можем сказать, что γ

— универсальна, если L(γ) =