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

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

5.7. Универсальные автоматы Уотсона–Крика 231

ствия со второй лентой, при чтении символа a ∈ V в верхней

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

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

при чтении символа ¯a в верхней дорожке первой ленты одно-

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

второй ленты. Отсюда, L

(M) = T S

Следствие 5.13. Каждый яз ык из RE является образом при

детерминированном ОПМ-отображении некоторого языка из

N1PWK(u).

5.7 Универсальные автоматы Уотсона–Крика

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

средством автоматов Уотсона–Крика (раздел 5.3) было бы ин-

тересно найти универсальный (конечный) автомат Уотсона–

Крика. Например, в силу теоремы 5.2 такой автомат будет уни-

версальным — по модулю слабого кодирования — для целого

класса машин Тьюринга.

Временно отложим обсуждение этого сюжета, а пока от-

метим, что конечный автомат Уотсона–Крика может служить

изящным пример ом «частично универсального» конечного ав-

томата, сконструированного в конце раздела 3.3.

Пусть M = (K, V, s

, F, P ) — конечный автомат, и x —

строка из V

∗

. Рассмотрим строку w = code(M)

, где запись

code(M) имеет тот же смысл, что и в разделе 3.3, а n = |x|.

Кроме того, рассмотрим строку xc

для m = |w| − |x| (т. е.

|w| = |xc

|). Обозначим через ρ универсальное отношение на

множестве K ∪ V ∪ {c, c

, c

}. Запишем строку xc

в верх-

нюю нить, а ст року w в нижнюю нить ленты Уотсона–Крика.

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

струированного в разделе 3.3, указывает способ определения

переходов автомата Уотсона–Крика, работающего с упомяну-

той выше лентой и распознающего строки xc

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

тогда, когда x ∈ L(M). Нижняя головка считыва ет копию кода

автомата M , записанную на нижней дорожке, недетерминиро-

вано выбирает переход sa → as

автомата M в соответствии с

232 5. Автоматы Уотсона–Крика

прочитанным верхней головкой символом a, и состояние авто-

мата Уотсона–Крика проверяет корректность связи состояний

автомата M, запоминая их. Как только на верхней дорожке

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

автомат M должен перейти в заключительное состояние для

корректного завершения разбора. Подробности конструкции

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

Рассмотрим теперь более простую «прогр амму» для M, в

которой последовательность из |x| копий кода M отделена от

«начальных данных» (строки x). В такой ситуации есть две

проблемы: довольно велика длина этой «программы» и распо-

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

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

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

мата Уотсон а–Крика двигаться в обоих направлениях. Тогда

будет достаточно всего одной копии code(M), и лента сможет

принять вид

code(M )c

, где m и p — такие целые числа, что

m > 1 и |xc

| = | code(M )c

| (на верхней нити есть по крайней

мере один символ c отмечающий конец ленты, и, кроме того,

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

вания длин). И снова конструкция оказалась по существу по-

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

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

увидеть конкретный автомат Уотсона–Крика, универсальный

в рассмотренном выше смысле.

Сперва договоримся об одном обозначении. Переход в ав-

томате Уотсона–Крика с перемещающейся в обоих направле-

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

правил: одно для верхней, а другое для нижней головки; для

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

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

(состояние является характеристикой автомата, а не каждой

из головок).

Для множества конечных автоматов, которые необходимо

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

5.7. Универсальные автоматы Уотсона–Крика 233

и алфавит V . Построим автомат Уотсона–Крика

= (K

, V ∪ K ∪ {c, c

, c

}, ρ

, q

0,u

, {q

}, P

в котором

1) ρ

= (V ∪ K ∪ {c, c

, c

}) × (V ∪ K ∪ {c, c

, c

}),

2) K

= {q

0,u

, q

0,u

, q

0,u

, q

}∪{[s], (s), (s)

, (s)

000

, (s)

, [s] | s ∈

K} ∪ {[sa] | s ∈ K, a ∈ V }, и

3) множество P

состоит из следующих правил перехода (пра-

вило вида sλ → s

λ в верхней позиции означает то, что верх-

няя головка не движется):

0,u

λ → q

0,u

s → sq

0,u

, s ∈ K, (1)

0,u

λ → q

0,u

a → aq

0,u

, a ∈ V, (2)

0,u

λ → q

0,u

s → sq

0,u

, s ∈ K, (3)



0,u

λ → [s

]λ

0,u

→ s

]



, (4)



[s]a → a[sa]



, s ∈ K, a ∈ V, (5)



[sa]λ → (s

)λ

[sa]s

→ s

)



, s, s

∈ K, a ∈ V, (6)



(s)λ → (s)

(s)s

→ s

(s)



, s, s

∈ K, (7)



(s)

λ → (s)

(s)

a → a(s)



, s ∈ K, a ∈ V, (8)



(s)

λ → (s)λ

(s)

→ s

(s)



, s, s

∈ K, (9)



(s)λ → [s]λ

(s)s → s[s]



, s ∈ K, (10)



(s)λ → (s)

000

(s) → (s)

000



, s, s

∈ K, (11)

234 5. Автоматы Уотсона–Крика



(s)

000

λ → (s)

a(s)

000

→ (s)



, s ∈ K, a ∈ V, (12)



(s)

λ → (s)λ

(s)

→ (s)s



, s, s

∈ K, (13)

(s)c → c[s]

(s)c

→ c

[s]

, s ∈ K, (14)

[s]λ → [s]λ

[s]s

→ s

[s]

, s, s ∈ K, s 6= s

, (15)

[s]λ → q

[s]s → sq

, s ∈ F, (16)



λ → q

s → sq



, s ∈ K, (17)



c → cq

λ → q



, (18)



λ → q

→ c



, (19)



λ → q

c → cq



. (20)

Возьмем теперь конкретный конечный автомат M = (K

, s

, F, P ), в котором K

⊆ K, V

⊆ V , и напишем «програм-

му» для M

, т. е. в верхней строке его входной ленты напишем

, а в нижней — code(M )c

, где числа m, p определяются

описанным выше способом.

Пока верхняя головка M

остается на месте, нижняя ищет

переход автомата M, в котором участвует текущий символ из

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

a → as.

Затем по правилам 5 и 6 моделируется один шаг работы авто-

мата M. В состоянии (s

) автомат M

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

шаг вправо по правилам 7, 8, 9 или влево по правилам 11,

12, 13 в поиске в ерного продолжения по правилу 10. Когда за-

канчивается строка x и верхняя головка доходит до символа c

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

5.7. Универсальные автоматы Уотсона–Крика 235

рез тройки вида sas

, можно предполагать, что в тот же самый

момент она доходит до символа c

, разделяющего в code(M)

переходы и конечные состояния), происходит переход на про-

верку того, является ли текущее состояние заключительным в

автомате M . Лишь при положительном ответе на это т вопрос

работа M

завершается корректно по правилу 16. Следовател ь-

но, xc

∈ L(M

) тогда и только тогда, когда x ∈ L(M). (Пра-

вила 17–20 используются для просмотра суффиксов c

, c

на

обеих дорожках.)

Доказательство теоремы 5.2 состоит из следующих шагов:

1) для грамматики Хомского G типа 0 строится три таких мор-

физма h

, h

, что L(G) = h





EQ(h

, h

)



∩ R



, где

EQ(h

, h

) обозначает множество равенств для h

, h

(т. е.

множество таких слов w, что h

(w) = h

(w)), а R — некото-

рый регулярный язык (теорема 3.16);

2) для построенных выше морфизмов h

, h

строится систе-

ма со склейкой определенного типа (когерентная), которая

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



EQ(h

, h

)



в верхних цепочках (теорема 4.12);

3) по этой системе со скл ейкой строится автомат Уотсона–Кри-

ка, распознающий язык h



EQ(h

, h

)



∩R (лемма 5.15); та-

ким образом, оставшегося морфизма (выше это h

, который

на самом деле является слабым кодированием) достаточно

для характеризации RE .

Все эти три шага конструктивны. Если теперь взять вместо

G универсальную грамматику G

типа 0, то получится авто-

мат Уотсона–Крика, являющийся универсальным в естествен-

ном смысле. Однако такой путь от универсальной грамматики

типа 0 к универсальному автомату Уотсона–Крика настолько

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

ным (не видно даже простого способа написать «программу»

для такой универсальной машины). Задача нахождения про-

стых конечных автоматов Уотсона–Крика, которые были бы

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

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

236 5. Автоматы Уотсона–Крика

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

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

тов Уотсона–Крика, универсальных для автоматов с ограни-

ченным числом состояний и входных символов.

Для конечного автомата Уотсона–Крика в 1-ограниченной

нормальной форме (из следствия 5.1 известно, что такие авто-

маты экви вален тны произвольным конечным автоматам Уот-

сона–Крика) M = (K, V, ρ, s

, F, P ) рассмотрим кодировку ви-

да

code(M) = [s





] . . . [s





][s

] . . . [s

в которой каждый блок [s





] — это символ, соответству-

ющий переходу s





→





из P (значит, один из эле-

ментов α

, β

является буквой, а второй пуст), а каждый блок

] — это символ, соответствующий заключительному состо-

янию из F .

При разборе молекулы x =

...a

...b

, a

, b

∈ V , 1 6 i 6 r,

r > 1, за один такт читается ровно один символ на одной из до-

рожек, таким образом, весь разбор состоит из 2r шагов. «Ско-

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

может быть сколь угодно большим. Таким образом, для со-

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

слить коды для M с символами в каждой нити последователь-

ности x и рассмотреть молекулу



code(M)a

. . . code(M )a

code(M)c code(M)

code(M)b

. . . code(M )b

code(M)c code(M)





bls(code(M), a

. . . a

bls(code(M), b

. . . b



(Отношение комплементарности содержит все пары из ρ плюс

все пары (α, α) для символов α, встречающихся в code(M ),

или α = c.)

Теперь универсальный конечный автомат Уотсона–Крика

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

деле 3.3 для обыкновенных конечных автоматов: прочи тать по-

следовательность code(M) на одной из двух нитей, выбрать

5.7. Универсальные автоматы Уотсона–Крика 237

переход вида





, закодированный символом [s





], смо-

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

должно выполняться β = λ, при работе на н ижн ей дорожке

должно выполняться α = λ); состояния универсального авто-

мата гарантируют корректную взаимосвязь состояний автома-

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

сти также, как и состояния M; движение по разным нитям идет

с разной скоростью; после достижения столбика





произво-

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

ным относительно M (т. е. состоянием, которому соответствует

некоторый символ [s] в code(M)); при положительном резуль-

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

в заключительное состояние.

Обозначив через M

автомат Уотсона–Крика, конструкция

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

∈ L

) тогда и только тогда, когда x ∈ L

(M),

т. е. свойство универсальности.

Приведенная выше «программа» w

довольно сложна (она

не контекстно-свободного типа из-за повторяющихся копий

code(M) на каждой из двух дорожек). Путь снижения слож-

ности исходной молекулы этого универсального автомата

Уотсона–Крика такой же, как и в случае обычных конечных

автоматов (там мы перешли к автоматам Уотсона–Крика):

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

матам Уотсона–Крика с тройной лент ой и тремя читающими

ее головками под контролем общего состояния.

Во-первых, в таком случае можно упростить форму «про-

граммы» w

: запишем на первой дорожке a

· · · a

, на второй

дорожке b

· · · b

и дополним их нужным количеством сим-

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

которой записаны 2r копий code(M ). Третья читающая голов-

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

code(M) переход, подходящий для символа на одной из двух

первых нитей. Отметим, что в такой ситуации «программа»

(code(M)) отделена от данных (молекулы x).

238 5. Автоматы Уотсона–Крика

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

головки в обоих направлениях (оставляя для двух п ервых голо-

вок лишь возможность движения в одну сторону), то будет до-

статочно всего одной копии code(M) (смотри описанную выше

конструкцию двустороннего конечного автомата Уотсона–Кри-

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

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

ных символов).

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

тали, касающиеся универсальных автоматов Уотсона–Крика с

двойными и тройным лентами.

Замечание 5.6. Мы исследовали зд есь только некоторые

основные вопросы об авт оматах Уотсона–Крика как распо-

знающих устройствах, существенно использующих новый

тип данных — ленты Уотсона–Крика, основанные на возни-

кающих в цепочках ДНК отношениях комплементарности.

Тем самым мы «уравновесили» проведенное в предыдущей

главе исследование порождающих устройств. Определив эти

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

теории авто матов программу исследований. Здесь мы, в основ-

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

зрения молек улярных вычислений: представления (т. е. ха-

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

выглядят ободряющими: большинство наших машин харак-

теризуют RE по модулю простого сжимающего устройства:

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

ОПМ в др угих. Такие сжимающие механизмы естественны

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

четырехбуквенного алфавита ДНК приходится иметь дело с

кодированием информации.

Есть много других задач для исследований. Упомянем

только некоторые из них.

1. Исследовать «чистые» семейства языков, связанных с ав-

томатами Уотсона–Крика (слово «чистые» означает: без ис-

пользования сжимающих механизмов). Что можно сказать

5.7. Универсальные автоматы Уотсона–Крика 239

об их соотношениях между собой и соотношениях между

ними и семействами из иерархии Хомского или из других

стандартных иерархий языков?

2. Улучшить, если возможно, представленные здесь характе-

ризации RE, используя более простые автоматы Уотсона–

Крика и/или более простые сжимающие механизмы.

3. Найти конкретные автоматы Уотсона–Крика, которые бы-

ли бы (по модулю слабого кодирования или других сжимаю-

щих механизмов) универсальными для классов всех машин

Тьюринга.

4. Рассмотрим детерминированные автоматы Уотсона–Крика

различных тип ов. Будут ли они строго слабее, чем неде-

терминированные? Детерминизм можно здесь определять

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

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

вида s

∈ δ(s,





), где строки x

, x

могут состоять из

любого числа символов, в том числе и быть пустыми).

5. Определить и исследовать классы сложности, основанные

на автоматах Уотсона–Кр ика. Существенная часть необхо-

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

мых структурах данных — лентах Уотсона–Кр ика, и можно

считать, что эта часть достается «даром» некоторую свобо-

ду, поскольку в последовательностях ДНК комплементар-

ность Уотсона–Крика проверяется автоматически. Поэто-

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

основанные на машинах Тьюринга и других строкоподоб-

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

ности Уотсона–Крика. Это направление особенно интерес-

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

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

применения молекул ДНК — или связанных с ними теоре-

тических моделей — для вычислений.

6. Определить и исслед овать меру дескриптивной сложности

для автоматов Уотсона–Крика и дл я их языков. Основными

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

240 5. Автоматы Уотсона–Крика

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

ле 5.1 как переписывающие правила). Вторая мера особенно

интересна для автоматов без состояний.

7. Все эти классы задач связаны с автоматами, введенными

в этой главе, а значит, и со структурами дан ных Уотсо-

на–Крика. Область задач, касающихся параллелизма воз-

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

открытой. По нашим оценкам, полное исп ользов ание этого

важного «козыря» молекул ДНК может привести к реши-

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

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

ная разрешимость за полиномиальное время.

Вообще, «фоном» для проводимых здесь исследований

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

реализации автомата Уотсона–Крика в любом из рассмотрен-

ных вариантов или в каком-либо другом виде, который еще

будет определен. Однако к такой проблеме можно подступить-

ся лишь в рамках междисциплинарного подхода.

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

Эта глава в основном базируется на раб оте [99], в которой бы-

ли введены автоматы Уотсона–Крика (во всех рассмотренных

выше вариантах, кроме 1-ограниченных). Конечные автома-

ты Уотсона–Крика рассматривались также в [98]. Обсуждение

универсальных автоматов Уотсона–Крика следует статье [209],

где введены 1-ограниченные автоматы.