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

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

6.3. Односимвольные системы вставки и удаления 261

→ α

для α

→ α

∈ P (3)

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

→ α

, 1 6 i 6 n. (5)

(Они сдвигают символ α

= # влево.)

Обозначим п олучен ную таким способом грамматику че-

рез G

Тогда для каждого вывода S =⇒

∗

w в грамматике G можно

найти вывод S#

=⇒

∗

w в G

для некоторого t > 0.

На основе G

построим ограниченную ВУ-систему

γ = (N ∪ T ∪ {#}, {a, c}, A, R, h)

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

Рассмотрим морфизм g, определяемый равенствами g(α

) =

i+1

a, 0 6 i 6 n. (В частности, пробел # кодируется как aca.)

Далее, A = {ac

a}, h(α

) = ac

i+1

a для терминального симво-

ла α

из G. Теперь составим множество R из следующих пра-

вил.

Для q-го правила в G

, r

: α

→ α

рассмотрим «зако-

дированное» правило

i+1

aac

j+1

a → ac

k+1

aac

p+1

и поместим в R правила

(ac

i+1

aa, λ/c

(2q−1)(n+1)

, c

j+1

aac

s+1

a), 0 6 s 6 n, (r

.1)

(ac

i+1

, λ/c

2(q−1)(n+1)

, aac

(2q−1)(n+1)+j+1

a), (r

.2)

(ac

2(q−1)(n+1)+i+1

aa, c

(2q−1)(n+1)+j−p

/λ, c

p+1

a), (r

.3)

(ac

k+1

, c

2(q−1)(n+1)+i−k

/λ, aac

p+1

a). (r

.4)

Заметим, что:

1) в G

нет правил вида #α

→ α

, значит, в предыдущих

правилах i > 1;

2) в то же время j, k, p > 0, причем они могут и равняться

нулю.

262 6. Системы вставки и удаления

Покажем, что L(G) = L(γ). В соответствии с приведенным

выше обсуждением достаточно показать, что

{w ∈ T

∗

| S#

=⇒

∗

w в G

для некоторых s, t > 0} = L(γ).

(⊆) Рассмотрим шаг вывода x =⇒ y в G с использованием

правила (унифицированного вида) r

: α

→ α

. То есть

x = x

=⇒ x

= y.

Строке x соответствует такая «кодированная» строка g(x), что

g(x) = g(x

)ac

i+1

aac

j+1

ag(x

Поскольку в начальной строке S#

число s достаточно вели-

ко, можно считать, что g(x

) 6= λ. Тогда, используя правила

.1) − (r

.4), получим

g(x) = g(x

)ac

i+1

aac

j+1

ag(x

)

=⇒ g(x

)ac

i+1

(2q−1)(n+1)+j+1

ag(x

)

=⇒ g(x

)ac

2(q−1)(n+1)+i+1

aac

(2q−1)(n+1)+j+1

ag(x

)

=⇒ g(x

)ac

2(q−1)(n+1)+i+1

aac

p+1

ag(x

)

=⇒ g(x

)ac

k+1

aac

p+1

ag(x

)

= g(y).

Следовательно, каждый вывод в G

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

помощью вывода в γ. Используя правила вида α

→ α

, по

каждому терминальному выводу строки w в G

можно найти

вывод строки #

g(w) в γ. Следовательно, h

−1



g(w)



= w, т. е.

L(G) ⊆ L(γ).

(⊇) Рассмотрим строку

z = ac

aac

a . . . ac

где 1 6 i

6 n + 1, 1 6 j 6 k.

Назовем блок ac

a при 1 6 i 6 n + 1 коротким, а при i >

n + 1 длинным.

В выписанной выше строке z все блоки короткие. К ней

можно применить только правило вставки вида (r

.1) из R , со-

ответствующее правилу r

из P . Пусть «закодированное» пра-

6.3. Односимвольные системы вставки и удаления 263

вило, ассоциированное с r

, имеет вид

aac

m+1

a → ac

aac

Используя правило (r

.1), получим

z =⇒ ac

. . . ac

m−1

aac

(2q−1)(n+1)+i

m+1

aac

m+2

. . . ac

a = z

Заметим, что при этом возник длинный блок

(2q−1)(n+1)+i

m+1

При использовании правила вида (r

.1) короткий блок, окру-

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

Точнее, выполняется вставка (2q − 1)(n + 1) новых символов c.

Поскольку при этом 2q − 1 нечетное, назовем этот блок нечет-

ным длинным блоком.

Единственным правилом из R, способным использовать

длинный блок в z

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

.2), в котором q то же, что и на предыдущем шаге. Обрат-

ный морфизм h

−1

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

рано или поздно правило (r

.2) придется применить. Это

означает, что подстрока

aac

(2q−1)(n+1)+i

m+1

строки z

заменится на

2(q−1)(n+1)+i

aac

(2q−1)(n+1)+i

m+1

a. (∗)

Следовательно, короткий блок ac

a заменится на длинный

блок ac

2(q−1)(n+1)+i

a. Поскольку число 2(q−1) четное, назовем

его четным длинным блоком.

Таким образом, получится строка, включающая в себя па-

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

ны которых однозначно определяются индексом q правила r

из G

Единственным правилом из R, способным использовать эти

длинные блоки, является правило (r

.3), заменяющее подстро-

264 6. Системы вставки и удаления

ку (∗) на

2(q−1)(n+1)+i

aac

т. е. нечетный длинный блок на короткий. Единственный воз-

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

короткий состоит в применении правила (r

.4), которое приво-

дит к ac

aac

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

вила

aac

m+1

a → ac

aac

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

ления (т. е. вычисления, строящего строку из (aca)

∗

g(T

∗

)). Сле-

довательно, если ac

a(aca)

=⇒

∗

(aca)

g(w) для некоторого

w ∈ T

∗

(только для таких строк w определено выражение

−1

(w)), то S#

=⇒

∗

w в G

, w ∈ T

∗

. Это означает, что w ∈

L(G), что и завершает доказательство.

Из доказательств теорем 6.2, 6.3 и 6.7 можно получить ре-

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

такие ВУ-системы γ

= (V

, T, −, R

) веса (1, 2; 1, 1) и веса (1, 1;

2, 0), а также такие ограниченные ВУ-системы, что для каждой

ВУ-системы γ = (V

, T, A

, R

) можно подобрать такое множе-

ство слов A(γ) в алфавите V

, что L(γ

) = L(γ) для γ

= (V

T, A(γ), R

). Итак, универсальная ВУ-система моделирует лю-

бую данную ВУ-систему γ, или каждая конкретная система γ

запускается как программа для устройства γ

. Эти результаты

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

грамматику G

= (N

, T, P

) типа 0 и построим эквивалент-

ную ей ВУ-систему так же, как это сделано в доказательствах

теорем 6.2, 6.3 (или 6.7). Поскольку в G

нет аксиом, в по-

лученной системе γ

их тоже не будет. При этом γ

окажется

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

ВУ-системы γ с тем же терминальным алфави том существу-

ет эквивалентная ей грамматика G = (N, T, S, P ) типа 0. Рас-

смотрим (так же, как это было проделано в конце раздела 3.3,

когда строи лась универсальная грамматика типа 0) код w(G)

для этой грамматики. В аксиомах BSE, Sc, использовавших-

ся в доказательствах теорем 6.2 и 6.3, соответственно, S заме-

ним на w(G)S. Затем, поскольку L(G

) = L(G) для G

= (N

6.3. Односимвольные системы вставки и удаления 265

T, w(G)S, P

) и L(G) = L(γ), L(G

) = L(γ

) для γ

, получен-

ной из γ

описанным выше способом, получим L(γ

) = L(γ),

что и означает выполнение свойства универсальности. Видно,

что в действительности р аботающая на γ

программа γ состо-

ит лишь из одной строки. Тот же результат остается верен и

для ограниченных ВУ-систем с той разницей, что единствен-

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

большим количеством пробелов (aca, при кодировании в до-

казательстве теоремы 6.7). Таким образом, благодаря суще-

ствованию универсальных машин Тьюринга и универсальных

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

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

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

циях вставки и удаления.

Доказательство теоремы 6.7 наводит на другое интересное

размышление, касающееся так называемого «мусора в ДНК».

Известно, что б´oльшая часть генома человека (около 97%) со-

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

рые не могут содержать значительного объема информации и

не выполняют никаких известных функций. «Объяснение» это-

го с точки зрения компьютерных наук дано в [ 315] . Не вдава-

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

том, что высшие формы жизни должны иметь в генотипе пол-

ную вычислительную силу для того, чтоб ы обладать эффек-

тивной иммунной системой. Но вычислительная полнота при-

водит к ненадежности, что опасно для самой жизни. Значит,

должна существовать система и спра влени я ошибок («убийца

неудачных копий»). Вывод: «возможно, что мусор в ДНК в

значительной степени состоит из след ов старых ошибок» [315].

Приведенное выше доказательство дает более «мирное»

объяснение: если нужно обеспечить высокую вычислитель-

ную сложность, то потребуется произвольно большое рабочее

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

довательности пустых символов (пробелов или aca, здесь);

во время вычисления пустое пространство перемешивается

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

266 6. Системы вставки и удаления

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

вольно длинная последовательность повторяющихся строк.

Короче, мусор в ДНК может пр едставлять собой множество

ячеек рабочей области «вычислительного устройства». Это

объясняет как его изобилие, так и тот факт, что он состоит из

повторов одной и той же короткой строки. В термин ах [315]

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

ук к исследованию ДНК и РНК может оказаться столь же

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

6.4 Использование только вставки

При разработке «компьютера», основанного на операциях

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

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

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

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

было отмечено в лемме 6.1(ii), применяя одни только опе-

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

Более того, как видно из теоремы 6 .6 в разделе 6.2, семейство

IN S

∗

DEL

сильно ограничено. Тем не менее, применяя мо-

дель с некоторыми сжимающими механизмами (например, с

прямыми и обратными морфи змами), можно вновь охаракте-

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

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

удаления с дополнительными механизмами (отличными от

вставки), чтобы получить языки из RE. Поэтому здесь мы

рассмотрим только семейства INS

DEL

, где n, m > 0, в том

числе, и с условиями n = ∗ или m = ∗.

Для того чтоб ы иметь понятие о размере и свойствах этих

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

тельства можно найти в [1, 236, 237, 317] (некоторые из этих

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

тельств можно найти в [249]).

1. F IN ⊂ INS

∗

DEL

⊂ INS

∗

DEL

⊂ · · · ⊂ INS

∗

DEL

⊂

CS.

6.4. Использование только вставки 267

2. Семейство REG несравнимо с семействами INS

∗

DEL

m > 0.

3. Семейства LIN и CF несравнимы со всеми семействами

IN S

∗

DEL

, m > 2, и INS

∗

DEL

4. Семейство INS

DEL

содержит неполулинейные языки.

5. Все семейства INS

∗

DEL

, m > 0 являются ант и-AFL.

Отметим различие между приведен ными выше пунктами 2

и 3. Как REG, так и LIN и CF несравнимы с INS

∗

DEL

. Ни-

же будет показано, что каждый регулярный язык можно по-

родить, используя только операцию вставки, т. е. эта операция

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

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

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

морфизмами, то достаточно будет контекстов длины 1.

Теорема 6.8. REG ⊂ INS

∗

DEL

Доказательство. Пусть L — регулярный язык, а M = (K, V,

, F, δ) — минимальный распознающий его детерминирован-

ный конечный автомат. Для каждого слова w ∈ V

∗

, определим

отображение ρ

: K −→ K так:

(q) = q

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

(q, w) `

∗

, λ), q, q

∈ K.

Очевидно, что если x

, x

∈ V

∗

таковы, что ρ

= ρ

, то для

каждых u, v ∈ V

∗

, строка ux

v лежит в L тогда и только тогда,

когда ux

v лежит в L.

Множество отображений из K в K конечно. Значит, и мно-

жество различных отображений ρ

тоже конечно. Обозначим

их количество через n

. Построим ВУ-систему γ = (V, V, A, R),

в которой

1. A = {w ∈ L | |w| 6 n

− 1},

2. R = {(w, λ/v, λ) | |w| 6 n

− 1, 1 6 |v| 6 n

, |wv| 6 n

, и

= ρ

268 6. Системы вставки и удаления

Из о пред елени я отображений ρ

и определений множеств A

и R немедленно следует, что L(γ) ⊆ L.

Предположим, что противоположное включение неверно, и

выберем во множестве L − L(γ) строку x минимальной длины.

Тогда x /∈ A. Значит, |x| > n

. Пусть x = zz

, где |z| = n

и z

∈ V

∗

. Если z = a

. . . a

, то у него n

+ 1 префик-

сов, а именно, λ, a

, a

, . . . , a

. . . a

. Но различных отобра-

жений ρ

всего n

. Следовательно, найдутся два таких пре-

фикса u

, u

слова z, что u

6= u

и ρ

= ρ

. Без ограниче-

ния общности можно предполагать, что |u

| < |u

|. Заменив

на u

, получим строку x

, снова лежащую в L. Посколь-

ку |x

| < |x|, а x — стр ока мин имальн ой длины во множестве

L − L(γ), получим x

∈ L(γ). Одн ако |u

| − |u

| 6 |u

| 6 n

т. е. если u

= u

, то (u

, λ/u

, λ) — правило вставки из R.

Это означает, что x

=⇒

x, т. е. x ∈ L(γ). Противоречие, из

которого следует, что L ⊆ L(γ).

Строгость включения очевидна (см., например, теорему 6.5

из раздела 6.2).

Теорема 6.9. Каждый регулярный язык является кодирова-

нием некоторого языка из семейства INS

∗

DEL

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

матика (а значит ее правила имеют вид X → aY или X → a

для X, Y ∈ N, a ∈ T ). Построим регулярную грамматику

= (N, N × T, S, P

в которой

= {X → (X, a)Y | X → aY ∈ P для a ∈ T, X, Y ∈ N}

∪ {X → (X, a) | X → a ∈ P для X ∈ N, a ∈ T }.

Кроме этого, рассмотрим кодирование h : (N × T )

∗

−→ T

∗

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



(X, a)



= a, X ∈ N , a ∈ T . Ясно,

что L(G) = h



L(G

)



, таким образом, достаточно доказать, что

L(G

) ∈ INS

∗

DEL

Рассмотрим множество

W = {x ∈ (N × T )

∗

| где x = x

(X , a)x

(Y, b)x

для

6.4. Использование только вставки 269

, x

∈ (N × T )

∗

, тогда X 6= Y }.

Ясно, что для каждого y ∈ W , выполнено |y| 6 card(N) и,

следовательно, множество W конечно. Построим ВУ-систему

γ = (N × T, N × T, A, R),

в которой

1. A = L(G

) ∩ (N × T )W ,

2. R =



(X, a), λ/(X

, a

) . . . (X

, a

), (Y, b)



| (X

, a

)

. . . (X

, a

) ∈ W , b ∈ T , X → aX

∈ P , X

→ a

Y ∈ P ,

→ a

i+1

∈ P для всех 1 6 i 6 k − 1



Включение L(γ) ⊆ L(G

) очевидно. Обратно, пусть x ∈

L(G

) — произвольная строка. Если x ∈ (N ×T )W , то x ∈ L(γ).

Если x /∈ W , то x = x

(X, a)x

(X, b)x

, x

∈ (N ∪ T )

∗

Ясно, что y = x

(X, b)x

∈ L(G

) и |y| < |x|. Выберем x

, x

таким образом, что (X, a)x

∈ W . Тогда y =⇒ x — корректный

вывод в соответствии с правилами из R. Если y ∈ (N × T )W ,

то x ∈ L(γ). В противном случае будем повторять описанную

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

z ∈ (N × T )W , что z =⇒ . . . =⇒ y =⇒ x, т. е. x ∈ L(γ), что и

завершает доказательство.

Если разрешены и прямые и обратные морфизмы, и, вдо-

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

стигается порождающая сила машин Тьюринга.

Теорема 6.10. Каждый язык L ∈ RE можно представить в

виде L = g(h

−1

)), где g — слабое кодирование, h — морфизм,

и L

∈ INS

DEL

Доказательство. Рассмотрим язык L ⊆ T

∗

, L ∈ RE, порож-

денный грамматикой Хомского G = (N, T, S, P ) типа 0, запи-

санной в нормальной форме Куроды. Тогда P содержит пра-

вила следующих двух типов:

1. X → Y Z, X → a, X → λ для X, Y, Z ∈ N , a ∈ T ,

2. XY → UZ для X, Y, U, Z ∈ N.

Вид этих правил показывает, что каждая строка из L(G)

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

270 6. Системы вставки и удаления

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

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

вол Q, чтобы подготовить подстроку XY для не контекстно

свободного правила из P , то заменим Q на Q

и сдвинем Q

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

лу Q

→ λ.)

Более того, можно предполагать, что на второ й фазе про-

изводится левосторонний вывод.

Добавим три новых символа #, $, c и построим ВУ-систему

γ =



N ∪ T ∪ {#, $, c}, N ∪ T ∪ {#, $, c}, {c

}, R



в которой R включает в себя следующие правила вставки:

(1) для каждого контекстно-свободного правила

r : X → x ∈ P поместим в R следующие правила:

(1.r): (α

X , λ/#$x, α

) для

∈ N ∪ {#, $, c}, 1 6 i 6 10, α

/∈ N{$},

/∈ N{$}N, α

/∈ N{$}NN , α

/∈ {#, $}, и

/∈ N{#$}N{#};

(2) для каждого не контекстно-свободного правила

r : XY → U Z ∈ P поместим в R следующие правила:

(2.r.1): (α

X , λ/$U Z, Y α

) для α

∈ N ∪ {#, $, c},

1 6 i 6 4, и α

/∈ N{$}N, α

/∈ N{$}, α

/∈ {#, $},

(2.r.2): (X$UZY, λ/#$, α) для α ∈ N ∪ {c},

(2.r.3): (X, λ/#, $UZY #$);

(3) для каждых X, Y ∈ N поместим в R следующие правила:

(3.XY.1): (α

XY #$, λ/X#, α

) для

∈ N ∪ {#, $, c}, 1 6 i 6 6, α

/∈ N{$}N, причем

если α

= X#, то α

= $;

(3.XY.2): (X, λ/#$, Y #$X#α) для α ∈ N ∪ {c},

(3.XY.3): ($Y #$X#, λ/$X, α) для α ∈ N ∪ {c}.

Все правила (1.r) назовем правилами типа 1, все прави-

ла (2.r.i) для каждого не контекстно-свободного правила r

из P и 1 6 i 6 3 назовем правилами типа 2, а все прави-

ла (3.XY.i) для X, Y ∈ N и 1 6 i 6 3 — правил ами типа 3.