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

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

7.6. Комментарии к библиографии 331

Раздел 7.1 основан на результатах [130] и введении и добав-

лении к [139]. Раздел 7.2 следует [239] с некоторыми модифи-

кациями в духе [139].

Один из главных вопросов, поднятых в [130], касался вы-

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

гда эти правила итерировались на конечном множестве началь-

ных строк. Ответ на него получен в [59], где было установлено,

что такая операция сохраняет регулярные языки. Доказатель-

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

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

нении регулярности (лемма 7.14), пр едставленное здесь, взято

из [269]. Аналогичная идея используется в [271], где доказыва-

ется, что регулярность сохраняется и «обобщенным сплетени-

ем», правила которого суть тройки r : (v

, v

; v

), применимые

к строкам вида x = x

и y = y

с результатом x

Правила сплетения вида u

, рассмотренные в дан-

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

, u

; u

и потому доказательство из [271] влечет лемму 7.14. Заметим,

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

тения, записанных в ви де u

, к соответствующему

множеству правил вида (u

, u

; u

) (с подходящим коди-

рованием символов «,» и «;»), мы не всегда получим регуляр-

ный язык из-за повторения строк u

и u

. Тем не менее, если

число строк u

, u

конечно, то регулярность будет сохраняться

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

вида u

. Общий результат в терминах AFL (лем-

ма 7.15) анонсирован в [270], в [271] он приведен в случае пра-

вил вида (v

, v

; v

), а со всеми подробностями изложен в [139].

Несколько более общая формулировка содержится в [272].

Основная лемма об универсальности доказана в [243] сра-

зу для расширенных H-систем. Расширенные H-системы были

введены в [258]. Характеризаци и регулярных языков в терми-

нах морфизмов (такие, как, например, теорема 7.5) найдены

в [109, 111, 239]. Лемма 7.18 появилась в [258]. Теоремы 7.8–

7.10 взяты из [243], теорема 7.7 — из [209].

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

Простые H-системы введены и исследованы в [212], где

можно найти и ряд результатов, не упомянутых в разделе 7.5

(они касаются дескриптивной сложности, алгебр аич еских ха-

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

регулярных языков и т. п.).

В [132] рассматривается одно обобщение SH-систем — систе-

мы с маркерами-строками: k-простая H-система — это тройка

γ = (V, A, Q), где V — алфавит, A — конечное подмножество

в V

∗

, а Q — конечное множество строк над V , длины мень-

шей или равной k, k > 1. Строки из Q играют ту же роль, что

и маркеры в простой H-системе: (uxv, u

) `

uxv

, x ∈ Q.

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

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

-про-

стыми H-системами, где k

6 k. В [132] доказано, что

SH = S

H ⊂ S

H ⊂ · · · ⊂

[

k>1

H = SLT.

Кроме того, установлена разрешимость вопроса о принадлеж-

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

H, k > 1. Дока-

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

ние k эффективно вычислимо.

Глава 8

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

Как мы уже видели в предыдущей главе, расширенные H-си-

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

порождают лишь регулярные языки. Поскольку нам хотелось

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

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

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

стем. Это с успехом было проделано для грамматик Хомского

и других порождающих механизмов в теориях регулируемых

переписывающих систем и грамматических систем. Вооружив-

шись соответствующими идеями этих теорий и идеями, пред-

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

ности (лемма 7.16), мы рассмотрим в данной главе ряд регу-

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

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

и значит, являются вычислительно полными. Из соответствую-

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

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

теров, основанных на сплетении».

8.1 От 1-сплетения к 2-сплетению

Расширенные H-системы, которые мы будем рассматривать в

данной главе (с регулируемым сплетением или другими ме-

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

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

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

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

с более реалистичной операцией 2-сплетения. В ее определении

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

(x, y) |=

(z, w)

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

тогда и только тогда, когда

x = x

, y = y

z = x

, w = y

для некоторых x

, x

, y

∈ V

∗

, где r = u

— пра-

вило сплетения.

Для H-схемы σ = (V, R) и языка L ⊆ V

∗

определим

(L) = {z ∈ V

∗

| (x, y) |=

(z, w) или (x, y) |=

(w, z)

для некоторых x, y ∈ L и r ∈ R}.

Далее можно определить σ

(L), i > 0, и σ

∗

(L) точно также,

как в начале раздела 7.3 были определены соответственно

(L), i > 0, и σ

∗

(L). Таким образом, можно повторить все

рассуждения из разделов 7.2–7.5, заменив операцию ` на |=.

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

(F L

, F L

), H

(F L

, F L

), EH

(F L

, F L

)

семейства языков, аналогичные семействам S

(F L

, F L

(F L

, F L

) и EH

(F L

, F L

) соответственно.

Скажем, что семейство языков F L замкнуто относитель-

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

языка L ⊆ V

∗

{c}V

∗

, где c /∈ V , L ∈ F L, язык

perm

(L) = {vcu | ucv ∈ L, u, v ∈ V

∗

}

также лежит в F L.

Лемма 8.1. Для каждого семейства F L

и семейства F L

замкнутого относительно объединения и отмеченной цикли-

ческой перестановки, имеем X

(F L

, F L

) ⊆ X

(F L

, F L

X ∈ {S, H, EH}.

Доказательство. Рассмотрим H-схему σ = (V, R) c R ∈ F L

Для каждого языка L ∈ F L

имеем σ

(L) = σ

(L), где σ

(V, R ∪ perm

(R)). Равенство очевидно, и R ∪ perm

(R) ∈ F L

благодаря свойствам F L

. Это доказывает все включения из

формулировки леммы.

Большинство результатов главы 7, касающихся семейств

(F L

, F L

), X ∈ {S, H, EH}, остаются справедл ивыми и в

случае семейств X

(F L

, F L

). Исключения составляют лем-

8.1. От 1-сплетения к 2-сплетению 335

мы 7.2, 7.4, 7.5. Правда, если от F L

, F L

из формулировок

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

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

и дл я семейств X

(. . . , . . . ). В леммах 7. 3 и 7.6 замкнутость

относительно ОПМ-отображений обеспечивает и замкнутость

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

эти леммы также остаются справедлив ыми для случая 2-

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

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

не математическими свойствами операции |=, а ее вычисли-

тельными свойствами. С этой точки зрения существенными

являются следующие факты:

1. Из лемм 7.14 и 8.1 следует, что H

(REG, F IN) ⊆ REG.

Аналогично, из леммы 7.15 имеем H

(CF, F IN) ⊆ CF .

Кроме того, лемма 7.18 остается верной для операции 2-

сплетения, REG ⊆ EH

(F IN, F IN). Это легко усмотреть

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

получающиеся в расширенной H-системе γ при операци-

ях 2-сплетения. Все они содержат нетерминальный символ

из N и символ Z, причем, даже вступая в новые сплетения,

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

лежащие в L. Следовательно, EH

(F IN, F IN) = REG.

2. Лемма 7.16 и при замене H

на H

остается справедливой,

т. е. каждый язык L ∈ RE, L ⊆ V

∗

, может быть запи сан

в виде L = L

∩ V

∗

для некоторого L

∈ H

(F IN, REG).

Это можно понять из доказательства леммы 7.16 (вторые

строки, полученные при 2-сплетении, не могут привести к

появлению строк из V

∗

, не лежащих в L). Здесь мы не ак-

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

ниже мы подробно обсудим данный вопрос.

3. Благодаря лемме 8.1 утверждение леммы 7.17 также вы-

полняется при замене H

на H

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

и для семейств EH

(F L

, F L

). В частности, имеем

(F IN, F IN) = REG, EH

(F IN, REG) = RE.

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

Обсуждение, приведенное после таблицы 7.3 можно так-

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

2-сплетениях: для того, чтобы добиться вычислительной пол-

ноты для систем с конечными компонентами, мы должны на-

делить наши модели дополнительными характеристиками.

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

Рассматривая H-системы в доказательстве леммы 7.16, можно

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

появления в правилах типа 1–6 подстрок w. Тем не менее, эти

подстроки неинформативны сами по себе (кроме правил ти-

па 6, в которых w ∈ T

∗

). Они являются произвольными стро-

ками над алфавитом N ∪ T ∪ {B}, и роль их заключается в

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

за ними, а именн о, о X, X

с левого конца первого терма спле-

тения и Y , Y

, α ∈ N ∪ T ∪ {B}, с правого конца второго терма

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

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

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

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

систем с регулируемым сплетением следующего типа.

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

это четверка

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

в которой V — алфавит, T ⊆ V , A — конечный язык над V ,

R — конечное множество троек вида p = (r; C

, C

), причем r

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

, а C

, C

—

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

∗

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

нечными компонентами.

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

∗

и p ∈ R , p = (r; C

, C

) определяем

(x, y) |=

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

(z, w),

каждый элемент из C

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

а каждый элемент из C

— в качестве подстроки в y; в том

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

случае, когда C

= ∅ или C

= ∅, никаких условий на x, соот-

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

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

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

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

L(γ) = σ

∗

(A) ∩ T

∗

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

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

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

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

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

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

, C

) из R. Если никаких ограничений

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

условно, эти числа являются конечными), мы заменяем [n] или,

соответственно, [m] на F IN.

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

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

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

с H-системами, основанными на операции |=.

Лемма 8.2. R E ⊆ EH

(F IN, pF IN).

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

G = (N, T, S, P ). Обозначим U = N ∪ T ∪ {B}, где B — новый

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

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

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

, Y, Z, Z

, Z

} ∪ {Y

| α ∈ U},

A = {XBSY, XZ, Z

, Z

, ZY }

∪ {ZY

, X

αZ | α ∈ U} ∪ {ZvY | u → v ∈ P }

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

Имитация : 1. (#uY $Z#vY ; {X}, ∅) для u → v ∈ P.

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

; {X}, ∅) для α ∈ U,

3. (X#$X

α#Z; {Y

}, ∅) для α ∈ U,

4. (#Y

$Z#Y ; {X

}, ∅) для α ∈ U,

5. (X

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

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

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

; {Y }, ∅),

7. (#Y $Z

#; ∅, ∅).

Эта конструкция, точнее, процедуры переброски и ими-

тации, переписанные для правил сплетения с разрешающими

контекстами, целиком взята из доказательства основной леммы

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

ровать правила из P в суффиксах первых термов сплетения.

Мы же до лжн ы уметь моделировать применение правила из P

в любом месте основной сентенциальной формы, а не только

на ее правом конце. Для этого введены прав ила групп 2, 3, 4

и 5, позволяющие нам осуществлять «ротацию» букв. Пр авил о

из группы 2 отрезает символ α с правого конца слова, Y

сохраняет информаци ю об этом символе, применение пр авил а

из группы 3 вводит α на левый край (вместе с X

), после чего

снова заменяется на Y (с помощью правила из группы 4),

а X

— на X (с помощью правил из группы 5). Таким образом

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

Правила из групп 6, 7 по зволяют, наконец, удалить огра-

ничители X и Y (первый из них — только при наличии B в

качестве соседа).

Разберем подробней, как эти идеи работают.

Имитируя вывод в G, начнем с XBSY . Ограничитель X и

его вариант X

, а также Y и его варианты Y

, β ∈ U, отмечают

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

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

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

держащиеся в R, требуют присутств ия символов Z, Z

, Z

во

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

слова берутся из A. Правило 1, при меняемое к XBSY и ZvY

при некотором S → v ∈ P , начинает имитацию вывода в G.

Далее, из слова Xx

uY и u → v ∈ P мы можем по лучи ть

vY , используя подходящее правило из группы 1:

(Xw|uY, Z|vY ) |=

(XwvY, ZuY )

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

для p = (#uY $Z#vY ; {X}, ∅), где u → v ∈ P и

w ∈ (N ∪ T )

∗

{B}(N ∪ T )

∗

Это соответствует шагу вывода x

=⇒ x

в G .

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

но получаем еще и слова ZuY пр и u → v ∈ P , которые не

используются в дальнейшем при имитации вывода в G.

К каждому слову XwαY , где α ∈ N ∪ T и

w ∈ (N ∪ T )

∗

{B}(N ∪ T )

∗

и, соответственно, к XwαY , где α = B и w ∈ (N ∪ T )

∗

, можно

применить также п одходящее правило группы 2, после чего —

соответствующие правила из групп 3 и 4. Наконец, задейство-

вав правило группы 5, мы получим слово XαwY . Символ α

был в результате пер еброшен с правого на левый конец слова,

что нам и требовалось:

1. (Xw|αY, Z|Y

) |=

(XwY

, ZαY ) при p = (#αY $Z#Y

;

{X}, ∅), где wα ∈ (N ∪ T )

∗

{B}(N ∪ T )

∗

, α ∈ N ∪ T ∪ {B};

2. (X|wY

, X

α|Z) |=

(XZ, X

αwY

) при p = (X#$X

α#Z;

}, ∅), где wα ∈ (N ∪ T )

∗

{B}(N ∪ T )

∗

, α ∈ N ∪ T ∪ {B};

3. (X

αw|Y

, Z|Y ) |=

αwY, ZY

) при p = (#Y

$Z#Y ;

}, ∅), где wα ∈ (N ∪ T )

∗

{B}(N ∪ T )

∗

, α ∈ N ∪ T ∪ {B};

4. (X

|αwY, X|Z) |=

Z, XαwY ) при p = (X

#$X#Z; {Y },

∅), где wα ∈ (N ∪ T )

∗

{B}(N ∪ T )

∗

, α ∈ N ∪ T ∪ {B}.

Как дополнительные результаты (уже не лежащие в мно-

жестве аксиом A) перечисленных выше сплетений получаются

слова ZαY , где α ∈ U, и если v 6= λ для всех правил u → v ∈ P ,

то еще и слово X

Заметим, что каждое слово, получавшееся до сих пор из

XBSY и не содержавшее символ Z, имело вид α

, где

(α

, α

) — одна из пар (X, Y ), (X, Y

), (X

, Y

), (X

, Y ), α ∈ U.

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

решающих контекстов в правилах сплетения из R, четко регу-

лируют работу γ.

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

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

ны воспользоваться правилами из групп 6, 7. Для применения

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

B — соседствовать с X:

1. (XB|wY, |Z

) |=

(XBZ

, wY ) при p = (XB#$#Z

; {Y }, ∅),

2. (w|Y, |Z

) |=

(w, Z

Y ) пр и p = (F

#$#Z

; {F

}, ∅),

где w ∈ (N ∪ T )

∗

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

слова XBZ

, Z

Y .

В общем, в γ можно построить любое терминальное слово,

какое может быть создано с помощью G, т. е. L(γ) ⊇ L(G).

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

быть порождено в γ, т. е. L(γ) ⊆ L(G).

Действительно, слова вида ZuY , возникающие по правилу

из группы 1 и связанные с u → v ∈ P , могут участвовать в

сплетении по правилу типа 1 только тогда, когда ZuY ∈ A,

а такая операция уже обсуждалась. Кроме этого, мы можем

выполнить сплетение

(Zu|Y, Z

|) |=

(Zu, Z

Y ) пр и p = (#Y $Z

#; ∅, ∅).

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

может, но лишь по тому же правилу, не давая ничего нового:

(Xw|Y, Z

|Y ) |=

(XwY, Z

Y ),

|Y, Z

|) |=

, Z

Y ).

Рассмотрим теперь строки ZαY, α ∈ U, получаемые при пе-

реброске. Их нельзя использовать как первые термы при спле-

тениях по правилам типов 1–6. Возникающая при сплетении

(Zα|Y, Z

|) |=

(Zα, Z

Y ) пр и p = (#Y $Z

#; ∅, ∅)

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

Y (см. предыдущий абзац) не приводит к появлению терми-

нальных строк. В качестве второго терма стр ока ZαY может

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

тогда, когда ZαY ∈ A.