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

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

8.4. Программируемые и развертывающиеся системы 371

Мы не только вернулись к c

#Y $Z#, но и впервые получи-

ли возможность применить сн ова правила A1, B1, C1, D1, E1

(имеющие первой слева подстроку c

#Y ). Таким образом, мы

можем продолжить с помощью любого из этих правил, либо

снова моделируя правило из P

, либо перебрасывая еще один

символ α с правого конца строки, ограниченной X, Y , на левый.

3. Окончание работы системы:

H. (удаление префикса XB

0. − − − − − −− c

#Y $Z#,

1. (c

#, λ/g

, Y ), c

Y $Z#,

2. (c

, λ/X, #g

), c

X#g

Y $Z#,

3. (λ, c

/λ, X#g

), X#g

Y $Z#,

4. (X, λ/B

, #g

), XB

Y $Z#,

5. (g

, Y/λ, $), XB

$Z#,

6. (g

$Z, λ/g

, #), XB

$Zg

7. (λ, g

/λ, $Zg

), XB

#$Zg

8. ($, Z/λ, g

#), XB

#$g

9. ($g

#, λ/Y, λ), XB

#$g

#Y,

10. (g

#, λ/Z, Y ), XB

#$g

#ZY,

11. (λ, g

/λ, #ZY ), XB

#$#ZY.

Лишь последнее правило сплетения может быть применено:

(XB

|wY, |ZY ) |= (XB

ZY, wY ).

J. (удаление ограничителя Y ):

0. − − − − − −− XB

#$#ZY,

1. ($, λ/h

, #ZY ), XB

#$h

#ZY,

2. (h

#Z, Y /λ, λ), XB

#$h

#Z,

3. (h

#, Z/λ, λ), XB

#$h

4. (h

, λ/Y, #), XB

#$h

Y # ,

5. (h

, λ/Z, Y #), XB

#$h

ZY #,

6. (λ, λ/h

, #$h

ZY ), XB

#$h

ZY #,

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

7. (h

#$, h

/λ, λ), XB

#$ZY #,

8. (λ, B

/λ, h

), Xh

#$ZY #,

9. (λ, X/λ, h

), h

#$ZY #,

10. (h

#, λ/Y, $), h

#Y $ZY #,

11. (λ, h

/λ, #Y $), #Y $ZY #.

Итак, мы можем сплести

(w|Y, ZY |) |= (w, ZY Y ).

Если строка w терминальная, она лежит в L(G); если нет —

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

сутствия ограничителей X, Y , а никакие дополнительные пра-

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

что использование правил мутаций в «ошибочных» направле-

ниях (например, при использовании правила 11 в предыдущей

группе перед правилами 8,9, в результате чего возникает пра-

вило сплетения α#Y $ZY # при α ∈ {X, B

, XB

}), не приво-

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

щая строка либо не содержит X и B

, если ранее применялось

правило XB

#$#ZY , либо если такой символ появляется, ни-

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

бо — XB

Y , и мы получаем λ, либо в ней остается X, и ни од-

на терминальная строка не возникает). Читатель может легко

проверить такие варианты. Правило #Y $ZY # изменено быть

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

Следовательно, получаем L(γ) = L(G).

Самые длинные строки u

, u

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

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

в правилах, полученных на шагах A4, A5, A9, B8, A

4, A

5, и

эта длина равна четырем. Итак, RE ⊆ EH

(F IN, rle[4]).

Заметим, что в предыдущем построении мы использовали

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

вола), и ни одного правила вида (u, α/β, v) для α 6= λ 6= β вклю-

чено не было. Используя и последние, можно немного упро-

стить конструкцию.

8.5. H-системы, основанные на двойном сплетен ии 373

Также весьма вероятно, что радиус системы можно умень-

шить по крайней мере до двух, как это пр оисходит во всех

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

струкцию еще более сложной, поэтому мы не станем здесь д ви-

гаться в этом направлении.

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

вставки-удаления. Например, самые длинные здесь — правила

из группы A5 вида (u, λ/α, v) при v = λ и |u| = 7. Безуслов-

но, этот параметр может быть улучшен; весьма вероятно, что

достаточно правил вида (u, α/β, v) при |u| 6 2, |v| 6 2.

С другой стороны, обеспечить постоянное присутствие

строк из A

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

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

из A

имеет вид Zx или xZ. Правила сплетения Z#x$Z#x и

x#Z$x#Z заставляют эти строки переходить с одного шага

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

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

следующим образом. В случае Z#x$Z#x нужно в C

добавить

правила

Z#x$Z# x, Z#x$c

Z#x,

и, кроме того, рассмотреть правила мутаций

($, λ/c

, Z), ($, c

/λ, Z).

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

на каждом шаге, и наличие Z#x$Z#x будет гарантировано.

То же самое может быть сделано для правил вида x#Z$x#Z.

Темой для исследования остаются другие варианты развер-

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

и от доступных в данный момент (или сплетаемых) строк.

8.5 H-системы, основанные на двойном

сплетении

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

тать аналогами матричных грамматик в теории регулируемых

переписывающих систем. Однако здесь мы имеем дело не с по-

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

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

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

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

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

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

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

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

Рассмотрим обычную расширенную H-систему γ = (V, T,

A, R) с конечным множествами A и R. Для x, y, w, z ∈ V

∗

, r

∈ R мы имеем

(x, y) |=

(w, z)

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

(x, y) |=

(u, v) и (u, v) |=

(w, z) при u, v ∈ V

∗

Для языка L ⊆ V

∗

определим

(L) = {w | (x, y) |=

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

(z, w)

при x, y ∈ L, r

, r

∈ R },

∗

(L) =

[

i>0

(L), где

(L) = L,

i+1

(L) = σ

(L) ∪ σ

(σ

(L)), i > 0.

Далее, мы свяжем с γ язык

(γ) = σ

∗

(A) ∩ T

∗

Через EH

(F IN, d[k]) обозначим семейство L

(γ) языков,

порожденных, как и ранее, расширенными H-системами γ =

(V, T, A, R) радиуса не больше k, k > 1.

Пример. Рассмотрим расширенную H-систему

γ = ({a, b, c, d, e}, {a, b, c, d}, {cabd, caebd}, R),

при R, содержащем правила сплетения

= c#a$ca#ebd, r

= ce#bd$b#d.

Возьмем строку вида ca

d, n > 1; одна из аксиом имеет такой

же вид при n = 1. Единственно возможное сплетение, включа-

8.5. H-системы, основанные на двойном сплетен ии 375

ющее эту строку, —

(c|a

d, ca|ebd) |=

(cebd, ca

n+1

d).

По определению операции, мы должны продолжить; един-

ственная возможность для этого

(ce|bd, ca

n+1

|d) |=

(ced, ca

n+1

d).

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

(ca

d, caebd) |=

(ced, ca

n+1

d).

Эту операцию можно повторить.

Другая возможность — начать с двух экземпляров аксио-

мы caebd:

(c|aebd, ca|ebd) |=

(ce|bd, caaeb|d) |=

(ced, caaebbd).

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

всех получаемых строках; эти строки не смогут участвовать в

сплетениях с строками вида ca

d, и значит, они н е приведут

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

Итак, получаем L

(γ) = {ca

d | n > 1}, — язык, не яв-

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

сплетения превосходят возможности простого сплетения.

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

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

рацию двой ного сплетения, совпадают с возможностями грам-

матик 0-типа.

Теорема 8.7. RE = EH

(F IN, d[2]).

Доказательство. Мы докажем только включение ⊆. Обрат-

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

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

ции двойного сплетения расширенную H-систему (или же ссыл-

кой на тезис Черча–Тьюринга).

Доказательство состоит из двух этапов.

(1) Рассмотрим грамматику G =



{S, B

, B

}, T , S,

P ∪ {B

→ λ, B

→ λ}



в нормальной форме Геффер-

та, задаваемой в теореме 3.5(2), т. е. с P , содержащим правила

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

вида S → uSv, S → x, при u, v, x ∈ (T ∪ {B

, B

})

Построим расширенную H-систему γ = (V, T, A, R) при:

V = T ∪ {S, B

, B

, X, Y, Z, Z

A = {SxS | S → x ∈ P, x ∈ (T ∪ {B

, B

})

∗

}

∪ {SuZvS | S → uSv ∈ P }

∪ {Z

, XY },

R = {S#$Su# ZvS, SZ#vS$#S | S → uSv ∈ P }

∪ {S#$#Z

, SZ

#$#S}

∪ {B

$X#Y, #B

Y $XB

∪ {B

$X#Y, #B

Y $XB

#}.

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

S#$Su#ZvS, SZ#vS$#S имитируют контекстно-свободные

правила S → uSv из P , а правила сплетения B

$X#Y,

Y $XB

#, B

$X#Y, #B

Y $XB

# — правила B

→

λ, B

→ λ соответственно; терминальные правила G имити-

руются с помощью аксиом SxS из A. Контекстно-свободные

выводы в G имитируются в γ в обратном порядке, начи-

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

правилом S → x) по направлению к концам.

Например, предположим, что имеется строка вида SwS при

w ∈ (T ∪{B

, B

})

∗

; аксиомы SxS — того же типa. Если

применить правило сплетения r

= S#$Su#ZvS, связанное с

некоторым правилом S → uSv ∈ P , получим

(S|wS, Su|ZvS) |=

(SZvS, SuwS).

Мы должны продолжить; поскольку не присутствует ни один

из символов X, Y, Z

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

ваться правилом r

= SZ#vS$#S, связанным с тем же самым

правилом S → uSv ∈ P :

(SZ|vS, Suw|S) |=

(SZS, SuwvS).

Двойное сплетение

(SwS, SuZvS) |=

(SZS, SuwvS)

8.5. H-системы, основанные на двойном сплетен ии 377

имитировало использование правила S → uSv в обратном

порядке. (Читатель может проверить, что начало (SwS|,

Su|ZvS) |=

(SwSZ|vS, |Su) |=

(SwSZSu, vS) не приводит к

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

Если к строке SwS применить правило r

= S#$#Z

, то

продолжить нужно по правилу r

= SZ

#$#S:

(S|wS, |Z

) |=

(SZ

|, w|S) |=

(SZ

S, w).

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

невозможно смоделировать в γ дополнительно ни одного пра-

вила вида S → uSv ∈ P , начав со строк и w).

Если к строке w, ограниченной или не ограниченной си м-

волами S, применить правило сплетения r

= B

$X#Y

(при условии, что подстрока B

есть в w, т. е. w = xB

y),

то продолжить нужно по правилу r

= #B

Y $XB

# (ника-

кое другое правило не применимо к промежуточным строкам),

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

(xB

y, X|Y ) |=

(x|B

Y, XB

|y) |=

(xy, XB

Y ).

Вхождение подстроки B

устраняется из исходной строки.

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

правило B

$X#Y ; удаляется вхождение подстроки B

Строки SZS, SZ

S не могут участвовать в сплетениях, при-

водящих к терминальным строкам, и это легко увидеть. Если

строка XB

Y ил и XB

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

не произведут ничего нового. Например, при r = #B

Y $XB

получаем:

(XB

Y, XB

Y ) |=

(XB

Y, XB

Y )

(XB

Y, XB

Y ).

Никакие дво йные сплетения других типов не могут приве-

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

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

P , удалению двух символов S с концов строки или применен ию

стирающих правил B

→ λ, B

→ λ. Порядок использо-

вания этих правил не важен. Следовательно, L(G) = L

(γ).

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

(2) Предыдущая конструкция позволяет модифицировать

«линейные» правила S → uSv из P , заменив их правилами ви-

да D → αEβ, где α, β ∈ T ∪ {B

, B

} и |αβ| = 1. Таким

образом возни кает грамматика, эквивалентная G, но содержа-

щая только правила с правой стороной длины два. Кроме того,

можно предположить, что для всех правил D → αEβ выпол-

няется D 6= E. Теперь нетерминальный алфавит больше, ис-

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

Линейная грамматика с несколькими нетерминальными

символами может быть имитирована с помощью расширен-

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

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

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

Более точно, рассмотрим линейную грамматику G = (N, T,

S, P ) и построим расширенную H-систему γ = (V, T, A, R) при

V = N ∪ T ∪ {Z, Z

A = {DxD | D → x ∈ P, x ∈ T

∗

}

∪ {DαZβD | D → αEβ ∈ P, где D, E ∈ N, α, β ∈ T ∪ {λ}}

∪ {Z

R = {E#$Dα#Zβ, EZ#βD$#E | D → αEβ ∈ P,

D, E ∈ N, α, β ∈ T ∪ {λ}}

∪ {S#$#Z

, SZ

#$#S}.

Читатель может легко проверить, что выводы в G имити-

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

ветствующих терминальным правилам D → x, и возвращаясь

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

убраны. Следовательно, L(G) = L

(γ). Ясно, что rad(γ) = 2.

Комбинируя эту идею со способом имитации стирающих

правил вида B

→ λ (заметим, что радиус правил сплете-

ния, связанных с ними, равен 1) получаем расширенную H-

систему радиуса 2.

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

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

В определении операций сплетения обоих типов ` и |=, ис-

пользовавшихся в предыдущих разделах, после сплетения двух

строк x, y и получения двух (в случае |=) возможно новых

строк z, w, разрешается снова использовать x или y в качестве

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

сплетения, более того, можно соединять x или y с z или w, т. е.

сплетать строки из одного «поколения» со строками из другого

«поколения». Кроме того, предполагается, что для каждой из

новых строк z и w возникает неограниченное число их копий.

Предположение, что у доступной строки имеется сколь

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

для каждой строки используется большое число ее копий.

Более того, производство большого числа копий последо-

вательности ДНК легко осуществимо с помощью метода

полимеразной цепной реакции (ПЦР). Это тоже уменьшает

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

большом числе процессоров-строк.

Тем не менее, существование нескольких копий каждой

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

операций. Например, после разрезания нескольких экзем-

пляров строки x на фрагмент x

, x

и изменен ия (в части

копий) x

, x

на некоторые x

, x

в пробирке будут находиться

строки всех четырех видов, x

, x

; может стать воз-

можной рекомбинация x

с x

или x

с x

, п риводящая к

возникновению нелегальных строк, «похожих» на легальные

строки x

или x

Можно избежать этой трудности, используя, по крайней ме-

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

этими числами во время ра боты системы. Это приводит нас

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

элементом которых связана некоторая кратность.

Формально мультимножество над множеством абстракт-

ных элементов X — это отображение M : X −→ N ∪ {∞};

M(x) — число экземпляров x ∈ X в мультимножестве M .

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

Если M (x) = ∞, то копий x неограниченное число. Множество

{x ∈ X | M(x) > 0} называется носителем M и обозначается

через supp(M). Обычн ое множество S ⊆ X можно воспри-

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

S(x) = 1 для x ∈ S и S(x) = 0 для x /∈ S.

Для двух мультимножеств M

, M

над X мы определим их

объединение равенством (M

∪ M

)(x) = M

(x) + M

(x), а их

разность — (M

−M

)(x) = M

(x)−M

(x), если x ∈ X, M

(x) >

(x) и оба числа M

(x), M

(x) конечны, если же x ∈ X, а

(x) = ∞, положим (M

−M

)(x) = ∞; для других строк x ∈

X разность M

− M

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

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

(x, M(x)) для x ∈ supp(M).

Например, M

= {(ab, 3), (abb, 1), (aa, ∞)} — мультимноже-

ство над {a, b}

∗

с носителем, состоящим из трех слов ab, abb,

aa; первое появляется в трех экземплярах, второе — лишь в од-

ном, а для aa присутствует неограниченное число копий. Если,

кроме то го, взять M

= {(ab, 1), (abb, 1), (aa, 17)}, то разность

− M

определена и равна {(ab, 2), (aa, ∞)}.

Расширенная µH-система — это четверка

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

в которой V — алфавит, T ⊆ V (терминальный алфавит), A —

мультимножество над V

с конечным supp(A) (аксиомы), R —

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

Для такой µH-системы и двух мультимножеств M

, M

над

∗

мы определяем

=⇒

тогда и тол ько тогда, когда существуют

x, y, z, w ∈ V

∗

, такие, что

(i) M

(x) > 1, (M

− {(x, 1)})(y ) > 1,

(ii) x = x

, y = y

, z = x

w = y

при x

, x

, y

∈ V

∗

∈ R ,

(iii) M





− {(x, 1)}) −{(y, 1)}



∪ {(z, 1)}



∪ {(w, 1)}.