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

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

10.4. Распределенные H-системы, изменяющиеся во времени 451

правилам сплетения, существенно зависит от внешних усло-

вий. Следовательно, в л юбой момент времени активно л ишь

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

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

тивные ферменты.

Изменяющаяся во времени распределенная H-система (сте-

пени n, n > 1) — это структура

Γ = (V, T, A, R

, R

, . . . , R

где

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

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

3) A — конечное п одмножество V

∗

(аксиомы) и

4) R

— конечные множества правил сплетения над V , 1 6 i 6

n. Множества R

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

стемы.

В момент k = n · j + i при j > 0, 1 6 i 6 n, для сплетения

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

Более точно, мы определяем

= A,

k+1

= σ

(i)

) для i ≡ k(mod n), k > 1,

где σ

(i)

= (V, R

), 1 6 i 6 n.

Таким образом, с шага k на следующий шаг k + 1 переда-

ется только результат сплетений строк из L

, выполненных по

правилам из R

, где i ≡ k(mod n). Строки из L

, которые не

могут вступить в сплетение, уничтожаются.

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

L(Γ) = (

[

k>1

) ∩ T

∗

Мы обозначаем через V DH

, n > 1, семейство языков, по-

рожденных изменяющимися во времени распределенными H-

системами степени не больше n, а через V DH

∗

— семейство

всех языков этого типа.

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

Мощность таких порождающих механизмов чрезвычайно

высока. Это объясняется тем, что с одного шага на другой пе-

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

на предыдущем шаге, а строки разных «поколений» сплетены

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

Для примера рассмотрим следующую систему степени 1

Γ = ({a, b, c}, {a, b, c}, {cab}, {a#b$c#a}).

Имеем

= {cab},

= {caab, cb} из (ca|b, c|ab) |= (caab, cb),

= {ca

b, cb} из (caa|b, c|aab) |= (ca

b, cb),

. . . . . . . . . . . . . . .

= {ca

k−1

b, cb}, k > 1.

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

L(Γ) = {ca

b | n > 0} ∪ {cb}.

Этот язык не является контекстно-свободным, и даже не лежит

в семействе MAT

Каждый регулярный язык может быть порожден изменяю-

щейся во времени H-системой степени 1. Это нетрудно устано-

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

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

сиомы с шага на шаг. Простой вид аксиом делает эту задачу

легко осуществимой. Таким образом, верна

Лемма 10.1. REG = EH

(F IN, F IN) ⊂ V DH

⊆ V DH

⊆

· · · ⊆ V DH

∗

⊆ R E.

Иерархия и з леммы 10.1 «схлопывается» самое большее на

седьмом уровне.

Теорема 10.8. RE = V DH

= V DH

∗

, n > 7.

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

па 0 с N ∪ T = {α

, . . . , α

n−1

}, n > 3, и P = {u

→ v

| 1 6 i 6

m}. Пусть α

= B — новый символ. Мы построим изменяющу-

10.4. Распределенные H-системы, изменяющиеся во времени 453

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

Γ = (V, T, A, R

, . . . , R

)

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

, Z, B} ∪ {Y

, Y

, X

| 0 6 i 6 n},

A = {XBSY, ZY, ZY

, ZZ, XZ} ∪ {Zv

Y | 1 6 i 6 m}

∪ {ZY

, ZY

, X

Z | 0 6 j 6 n} ∪ {X

Z | 1 6 j 6 n}

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

= {#u

Y $Z#v

Y | 1 6 i 6 m} ∪ {#Y $Z#Y, Z#$Z# }

∪ {#Y

$Z#Y

| 1 6 j 6 n},

= {#α

Y $Z#Y

| 1 6 j 6 n} ∪ {#Y $Z#Y

, Z#$Z#}

∪ {#Y

$Z#Y

| 1 6 j 6 n},

= {X#$X

#Z | 1 6 j 6 n} ∪ {#Y

$Z#Y, Z#$Z#}

∪ {#Y

$Z#Y

| 1 6 j 6 n},

= {#Y

$Z#Y

j−1

| 1 6 j 6 n} ∪ {#Y $Z#Y, Z#$Z#},

= {X

#$X

j−1

#Z | 1 6 j 6 n} ∪ {#Y $Z#Y, Z#$Z#},

= {#Y

$Z#Y, #Y

$ZZ# , #Y $Z#Y

, Z#$Z#}

∪ {#Y

$Z#Y

| 1 6 j 6 n},

= {X

#$X#Z, X

B#$#ZZ, #Y

$Z#Y, Z#$Z#}

∪ {#Y

$Z#Y

| 1 6 j 6 n}.

Эта система работает следующим образом.

Рассмотрим строку вида XwY , w ∈ (N ∪ T ∪ {B})

∗

(в част-

ности, для аксиомы XBSY w = BS).

Если w = w

, 1 6 i 6 m, то первая компонента может

смоделировать правило u

→ v

∈ P в суффиксе w. Строку

XwY можно передать в R

и неизмененной благодаря прави-

лу #Y $Z#Y . Аналогично, используя правило Z#$Z#, можно

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

редать из R

в R

. То же самое верно для всех пар последова-

тельных компонент.

Строка XwY в R

может вступить в два сплетения:

(Xw

|α

Y, Z|Y

) |= (Xw

, Zα

Y ) для w = w

, 1 6 j 6 n,

(Xw|Y, Z|Y

) |= (XwY

, ZY ).

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

Строка Xw

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

(X|w

, X

|Z) |= (XZ, X

) (∗)

при некотором i, 1 6 i 6 n.

Строка вида X

, 1 6 i, j 6 n, войдет в R

, R

в сплете-

ния, которые на единицу уменьшат как i, так и j, произведя

таким образом X

i−1

j−1

Строка X

, 1 6 i, j 6 n, преобразуется в R

в X

и далее в R

— в X

. Компонента R

, не изменив, передаст

эту строку в R

, где Y

снова будет заменен на Y

, а R

вернет

его обратно, произведя X

. Компоненты R

, R

снова на

единицу уменьшат индексы X и Y . В конечном счете индекс

одного из X, Y достигнет 0. Имеется три возможности.

1) R

получает строку X

при j > 1. Единственное при-

менимое правило — #Y

$Z#Y

. Строка X

передается в

, где принимает прежний вид X

. Снова Y

заменяет-

ся на Y

, затем R

возвращается к строке X

, которая и

попадает в R

. Компонента R

производит X

j−1

. В R

ни

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

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

можно.

2) R

получает строку X

при i > 1. Если Y

заменить на

Y , то строка X

xY не сможет вступить в сплетение в R

. То

же самое произойдет и при удалении Y

. Таким способом ни

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

3) R

получает строку X

. (Это означает, что у строки

, возникающей после сплетения (∗), i = j, зна -

чит, символ α

, удаленный с правого конца строк и, был

затем введен с левого конца.) Если R

заменит Y

на Y ,

то единственное продолжение в R

будет состоять в замене

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

процесс в целом. Если R

удалит Y

, а R

заменит X

на

X, то полученная строка не сможет пройти через R

, и

значит, окажется потерянной. Если же R

удалит Y

, а

— X

B, то возникшая строка без маркеров не сможет

вступить в дальнейшие сплетения. Если она терминальная,

10.4. Распределенные H-системы, изменяющиеся во времени 455

то принадлежит L(Γ), в противном случае, оказывается

потерянной.

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

и переброски можно смоделировать в Γ любой вывод из G.

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

Предположим теперь, что в R

была создана строка XwY

Если R

заменит Y

на Y , то строка XwY неизмененной прой-

дет через R

и R

. Затем R

произведет XwY

, а R

вернется

к XwY , и мы прибудем обратно в R

с XwY .

Если XwY

сплетется в R

по правилу X#$X

#Z, 1 6

j 6 n, возникнет строка X

. О на будет задержана в R

где никакое сплетение с ней неосуществимо.

Строки, полученные при упоминавшихся выше сплетени-

ях и содержащие Z, могут пройти от одной компоненты до

другой благодаря правилам Z#$Z# (а также правилам, ис-

пользующим символы Y, Y

и т. п.). Если строки этого вида и

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

ми, содержащими Z: с аксиомами или со строками, являющи-

мися побочным продуктом других сплетений. Таким образом,

возникшие строки будут содержать Z, а значит, ни одну терми-

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

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

согласно правилу #α

Y $Z#Y

, 1 6 j 6 n,

мы получим строку Zα

Y . Через R

− R

она сможет пройти

неизмененной. В R

можно выполнить

(Z|α

Y, Z|v

Y ) |= (Zv

Y, Zα

Y ),

если α

→ v

есть i-е прави ло P . Видно, что при этом воспро-

изводятся те же строки.

Читатель может прослед ить за эволюцией других строк ти-

па Zα

Y . Результат будет аналогичным: невозможно создать

ни одной терминальной строки, не лежащей в L(G). Таким об-

разом, L(G) = L(Γ).

Константа 7 в равенстве RE = V DH

вероятно может быть

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

нии, помня о желании уменьшить размеры компонент. Как

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

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

цель может быть достигнута: в компонентах изменяющихся во

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

три правила сплетения.

Теорема 10.9. Каждый рекурсивно перечислимый язык

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

ленной H-системой, компоненты которой содержат не более

трех правил сплетения.

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

па 0 с N ∪ T = {α

, . . . , α

n−1

}, n > 3, и P = {u

→ v

| 1 6 i 6

m}. Введем новый символ α

= B. Мы построим изменяющу-

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

Γ = (V, T, A, R

, . . . , R

2n+m+2

в которой

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

, Z, B},

A = {XBSY, ZY, ZY

, ZZ} ∪ {ZvY | u → v ∈ P }

∪ {Xα

Z | 1 6 i 6 n},

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

= {#u

Y $Z#v

Y, #Y $Z#Y, Z#$Z#}, 1 6 i 6 m,

m+2j−1

= {#α

Y $Z#Y, #Y $Z#Y

, Z#$Z#}, 1 6 j 6 n,

m+2j

= {Xα

#Z$X#, #Y

$Z#Y, Z#$Z#}, 1 6 j 6 n,

m+2n+1

= {XB#$#ZZ, #Y $Z#Y

, Z#$Z#},

m+2n+2

= {#Y $ZZ#, #Y

$Z#Y, Z#$Z#}.

За этой конструкцией вновь скрывается идея имитации и

переброски. Компоненты R

, 1 6 i 6 m, применяют на пра-

вом конце строк вида XwY , начиная с XBSY , пра вил а из P .

Компоненты R

m+2j−1

, 1 6 j 6 n, удаляют одно вхождение со-

ответствующего символа α

с правого конца строк, в то время

как парные им компоненты R

m+2j

, 1 6 j 6 n, заново вводят

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

, m+1 6 i 6

m + 2n, циклически переставляют строки, делая возможным

имитацию правил из P в любой желаемой позиции. Компонен-

ты R

m+2n+1

, R

m+2n+2

удаляют концевые маркеры X (только

при наличии B, а значит, в пр ави льно й перестановке) и Y . Во

10.4. Распределенные H-системы, изменяющиеся во времени 457

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

для перехода неизмененных строк на следующий шаг. Это пра-

вила — #Y $Z#Y в R

, 1 6 i 6 m, #Y $Z#Y

и #Y

$Z#Y , че-

редующиеся в R

m+2j−1

, R

m+2j

, 1 6 j 6 n, и R

m+2n+1

, R

m+2n+2

а также правила Z#$Z#, присутствующие во всех компонен-

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

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

ния, вводящие символ α

в строку, из которой не был ранее

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

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

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

Рассмотрим строку XwY и предположим, что с ней рабо-

тает компонента R

. Правило #Y $Z#Y не изменяет ничего,

оно только передает строку следующей компоненте. К строке,

попавшей в компоненту R

, 1 6 i 6 n, можно применить пра-

вило #u

Y $Z#v

Y , при этом ограничивающие маркеры X, Y в

строке сохранятся.

Достигнув R

m+1

, строка вида XwY может вступить в спле-

тение

(Xw|Y, Z|Y

) |= (XwY

, ZY )

или, если w = w

, в сплетение

(Xw

|α

Y, Z|Y ) |= (Xw

Y, Zα

Y ).

В первом случае XwY

может войти в следующей компоненте

m+2

в два разных сплетения :

(Xw|Y

, Z|Y ) |= (XwY, ZY

(Xα

|Z, X|wY

) |= (Xα

, XZ).

Благодаря первому мы возвращаемся к XwY , переходящей

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

строка Xα

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

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

Xα

исключается из дальнейшего процесса, и это предот-

вращает производство «неправильных» строк: символ α

был

введен слева от w, а самый правый в w α

до этого стерт не

был.

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

Во втором случае, когда α

был удален из w

, строка

Y достигает R

m+2

, где возможно единственное сплетение:

(Xα

|Z, X|w

Y ) |= (Xα

Y, XZ).

Строка Xα

Y — корректная циклическая перестановка

Y , снова ограниченная X, Y .

Следовательно, мы передаем в R

m+3

строку вида XzY .

Случай j = 1 аналогичен случаю произвольного j, 1 6 j 6 n,

значит, компоненты R

m+2j−1

, R

m+2j

либо выполняют требуе-

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

m+2n+1

Строка вида XwY может участвовать в R

m+2n+1

в двух

сплетениях:

(Xw|Y, Z|Y

) |= (XwY

, ZY ),

(XB|w

Y, |ZZ) |= (XBZZ, w

Y ), если w = Bw

В первом случае в R

m+2n+2

возможно только одно сплетение:

(Xw|Y

, Z|Y ) |= (XwY, ZY

Следовательно, мы неизмененной передаем строку XwY в R

завершая цикл. Во втором случае тоже можно воспользоваться

лишь одним правилом в R

m+2n+2

|Y, ZZ|) |= (w

, ZZY ).

Строка w

не помечена X, Y , и значит, не сможет вступить в

новые сплетения при ее передаче в R

. В сл учае нетерминаль-

ности она теряется. Следовательно, любой вывод из G можно

воспроизвести в Γ, следуя обычной процедуре имитации и пере-

броски. Как и в доказательствах предыдущих разделов, из «по-

бочных продуктов» сплетений, не имеющих вида XwY, XwY

терминальные строки, не лежащие в L(G), возникнуть не мо-

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

Для завершения доказательства остается заметить, что

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

сплетения.

10.5. Вычислительно полные H-системы 459

10.5 Классы вычислительно полных H-систем

Здесь мы перечислим те классы H-систем, которые, как было

доказано в главах 8, 9, 10, характеризуют рекурсивно перечис-

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

правил сплетения. Мы собрали их в четыре группы:

A. Управление тип а регулируемого переписывания:

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

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

3) расширенные H-системы с локальными мишенями,

4) расширенные H-системы с глобальными мишенями,

5) программируемые расширенные H-системы,

6) расширенные H-системы с двойным сплетением,

7) упорядоченные H-системы.

B. Другие управляющие механизмы:

1) расширенные H-системы, использующие мультимноже-

ства,

2) развертывающиеся расширенные H-системы,

3) расширенные H-системы с отображением годности.

C. Распределенные архитектуры:

1) сплетающие грамматические системы,

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

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

4) изменяющиеся во времени распр еделен ные H-системы.

D. Использование цикл ическ их строк :

1) расширенные циклическ ие H-системы.

10.6 Комментарии к библиографии

Сплетающие грамматические системы из раздела 10.1 были

введены в [61], где характеризуется семейство RE. Для этого

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

нентами. Теоремы 10.1 и 10.2 взяты из [244]. Теорема 10.3 —

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

из [113], где к тому же можно найти родственные результаты

(LIN ⊆ SGS

(REG), CF ⊆ SGS

(REG)).

Распределенные H-системы из раздела 10.2 были в нерас-

ширенном случае введены в [54]. Первые компоненты там ис-

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

веденных другими компонентами. (При таком подходе в тео-

реме 10.4, к примеру, потребуется еще одна дополнительная

компонента). В [54] доказано, что CDH

∗

= RE. В [355] этот

результат улучшается до CDH

= RE, далее в [248] доказы-

вается, что CDH

= RE. Усиление до трех компонент (теоре-

ма 10.4) получено в [274]. Доказательство теоремы 10.4 взято

из [252] (оно немного проще, чем доказательство в [274]). Тео-

ремы 10.5 и 10.6 — из [253].

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

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

логичный теореме 10.7. Случай разделенных систем рассмат-

ривается в [248]. Там же доказана теор ема 10.7.

Изменяющиеся во времени распределенные H-системы так-

же вводятся в [248], где можно найти доказательство теоре-

мы 10.9. Теорема 10.8 взята и з [252]. Недавно в [200] было со-

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

рактеризуются изменяющимися во времени H-системами сте-

пени 2. Это значительно улучшает результат теоремы 10.8.

В [208] введена некая разновидность распределенных H-си-

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

грамматическим системам из [50, 51] и используют вместо |=

отношение 1-сплетения `. На каждом этапе стр ока, получен-

ная на предыдущем шаге, соединяется с аксиомой. Компонен-

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

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

нента работает столько, сколько сможет (это — t-режим вывода

в грамматическ их системах, [50, 51]). Расширенные распреде-

ленные H-системы этого типа с тремя компонентами характе-

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

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