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

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

8.7. Результаты об универсальности 391

h(L(γ

)) дл я любой данной системы γ. Мы не рассматриваем

здесь этот случай, поскольку уже предполагается, что алфа-

вит ограничен четырьмя буквами алфавита ДНК (а значит,

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

ми алфавитами).

Начав доказательства лемм 8.2, 8.3, 8.5, 8.8, следствия 8.3,

теорем 8.5, 8.6, 8.7 и леммы 8.10 с универсальной грамматики

Хомского типа 0, мы получим H-системы нужных типов, ком-

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

тик, а значит, постоянны. Более того, эти H-системы обладают

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

тат важен для ДНК-вычислений, и мы докажем его довольно

подробно. Кроме того, мы увидим, что при переходе от (универ-

сальной) грамматики типа 0 к расширенной H-системе упомя-

нутых типов понадобятся всего два вспомогательных символа.

Более точно, верен следующий общий результат.

Лемма 8.14. По данной расширенной H-системе γ одного из

восьми указанных выше типов 1–8 с общим алфавитом V и

терминальным алфавитом T (и конечными множествами ак-

сиом и правил сплетения) можно построить расширенную H-

систему γ

того же типа с общим алфавитом T ∪ {c

, c

} и

терминальным алфавитом T , такую, что L(γ) = L(γ

Доказательство. Если V − T = {Z

, . . . , Z

}, рассмотрим мор-

физм h : V

∗

−→ (T ∪ {c

, c

})

∗

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

h(Z

) = c

для 1 6 i 6 n,

h(a) = a дл я a ∈ T.

Построим систему γ

с общим алфавитом T ∪ {c

, c

} и дру-

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

нения морфизма h к компонентам γ. (Например, для каждой

аксиомы x из γ в γ

в качестве аксиомы вводится h(x), а для

каждого правила сплетения u

из γ — правило спле-

тения h(u

)#h(u

)$h(u

)#h(u

). Аналогично поступаем с раз-

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

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

системах — в последнем случае старые маркеры c

, c

из до-

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

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

символами c

, c

Равенство L(γ) = L(γ

) следует из того, что во всех компо-

нентах системы γ

(независимо от ее типа) блоки c

, 1 6 i 6

n никогда не разбиваются при операциях сплетения (или ре-

дактирующих операциях в случае развертывающихся систем)

и ведут себя так же, как и соответствующие символы Z

Заметим, что в доказательстве этой леммы мы переходим

от символов Z

к строкам c

, а значит, пол учаем систему γ

с большим радиусом, чем у γ (но с тем же числом аксиом). Кро-

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

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

ны). Именно поэтому при определении расширенных H-систем

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

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

доказательства теорем 8.1, 8.2. Способ проверки из замеча-

ния 8.2 переносится без особых затруднений (по крайней мере,

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

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

символами, а с несколькими. Таким путем можно уменьшить

длину кодировок для нетерминальных символов в γ. Соотно-

шение между число м нетерминальных символов и длинами их

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

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

Теперь мы готовы привести один из главных c точки зрения

ДНК-вычислений резул ьтатов данной главы. Для точности в

деталях и ссылках мы явно формулируем его для µH-систем,

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

исследовавшихся ранее.

Теорема 8.9. Для каждого данного алфавита T существу-

ет расширенная µH-система (µ[1], F IN) типа лишь с двумя

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

классе расширенных µH-систем типа (µF IN, F IN) с терми-

нальным алфавитом T .

8.7. Результаты об универсальности 393

Доказательство. Рассмотрим алфавит T и два разных симво-

ла c

, c

, не лежащих в T .

В главе 3 уже говорилось о том, что для класса грамматик

Хомского типа 0 с данным термина льн ым алфавитом суще-

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

, T, P

), что для любой данной грамматики G = (N, T, S, P )

существует слово w(G) ∈ (N

∪ T )

(«код» G), такое, что

L(G

) = L(G) для G

= (N

, T, w (G), P

). (Язык L(G

) со-

стоит из всех терминал ьных слов z, таких, что w(G) =⇒

∗

при использовании правил из P

Для данной универсальной грамматики G

= (N

, T, P

)

типа 0, мы следуем конструкции из доказательства леммы 8.10,

получая расширен ную µH-систему γ

= (V

, T, A

, R

), в кото-

рой не рассматривается аксиома (кратности 1) w

= X

Y SX

Заметим, что все остальные аксиомы в A

(и имеющие беско-

нечную кратность), а также правила из R

зависят только от

, T , и P

, и значит, постоянны.

Теперь, как и в доказательстве леммы 8.11, перейдем от γ

к γ

= (V

, T, A

, R

). Поскольку A

содержит только аксиомы

бесконечной кратности, A

содержит лишь одно слово, опреде-

ляемое в доказательстве леммы 8.11 с помощью z и имеющее

бесконечную кратность.

Следуя доказательству леммы 8.14, кодируем все символы

из V

− T словами над {c

, c

}. Возникающая система

= ({c

, c

} ∪ T, T, A

, R

)

и является искомой универсальной µH-системой.

Действительно, возьмем произвольную расширенную µH-

систему γ

= (V, T, A, R). Поскольку L(γ

) ∈ RE, существует

грамматика типа 0 G

= (N

, T, S

, P

), такая, что L(γ

) =

L(G

). Построим w(G

) — код G

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

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

слово

= X

Y w(G

соответствующее аксиоме w

из доказательства леммы 8.10 и

закодируем его над {c

, c

}∪T точно так же, как ранее аксиомы

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

. Обозначим полученное слово через w(γ

). Тогда L(γ

) =

L(γ

) для γ

= ({c

, c

} ∪ T, T, {(w(γ

), 1)} ∪ A

, R

Можно легко в этом убедиться. В доказательстве лем-

мы 8.10 система γ моделирует работу G, начиная с аксиомы S

из G, записанной в виде X

Y SX

. Если вместо S взять про-

извольное слово x над алфавитом из G, то в γ мы получим

в точности язык терминальных слов y, таких, что x =⇒

∗

в G. Если начать с универсальной грамматики G

, а S заме-

нить кодом w(G

) грамматики G

типа 0, эквивалентной γ

то система γ

, связанная указанным образом с универсаль-

ной грамматикой G

, будет имитировать работу G

, начиная

с w(G

). Следовательно, L(γ

) = L(G

) = L(γ

)

для G

= (N

, T, w (G

), P

Очевидно, A

содержит только одну строку, и значит, γ

—

система типа (µ[1], F IN).

Заметим, что универсальная µH-система γ

, предлагаемая

в доказательстве теоремы 8.9, имеет лишь одну аксиому (то же

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

с локальными или глобальными мишенями, с отобра жениями

годности и для программируемых систем; в случае разверты-

вающихся H-систем, A

будет пустым и здесь потребуется до-

бавить строку XB

w(G

)Y , содержащую «программу» γ

, вме-

сто строки XB

SY в доказательстве теоремы 8.6). Более того,

и запускаемая на нашем «компьютере» «программа» также со-

стоит только из одной строки-аксиомы.

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

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

проблемы, сформулированной после следствия 8.1: суще-

ствует такое число n, при котором верен результат вида

RE = EH

([n], p[2]). Это можно доказать следующим обра-

зом. Начнем построение в доказательствах лемм 8.2 и 8.3

с универсальной грамматики типа 0. Получим H-систему с

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

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

чтобы породить данный язык L ∈ RE, мы должны ввести еще

одну аксиому типа XBw(G)Y , где G — грамматика типа 0,

8.7. Результаты об универсальности 395

порождающая L, а w(G) – код G. Радиус правил остается

неизмененным, а число аксиом ограничено.

Таким образом, вопрос можно переформулировать так: ка-

ково наименьшее n, при котором RE = EH

([n], p[2])?

Доказательство теоремы 8.9 эффективно, так как в нем кон-

структивно строится расширенная µH-система, универсальная

для класса µH-систем или, непосредственно, для класса грам-

матик Хомского типа 0 или машин Тьюринга. Начав с уни-

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

универсальную расширенную µH-систему.

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

оценим число правил сплетения, получающихся при примене-

нии конструкции из доказательства теоремы 8.9.

Рассмотрим универсальную машину Тьюринга M из класса

UTM(m, n) (см. раздел 3.3), имеющую p переходов. Для каж-

дого перехода машины M (заданного в виде переписывающего

правила, как в разделе 3.3, или другим подходящим способом)

мы строим в доказательстве леммы 8.10 примерно (n + m)

правил типа 1 и (n + m) правил типа 2. Мы получаем в общей

сложности

= p



(n + m)

+ n + m



правил (в качестве алфавита рассматриваются только ленточ-

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

требоваться дополнительные вспомогательные символы). Кро-

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

= (n + m)

+ (n + m)

правил типа 3, 4, 5, 6. Всего получается приблизительно

= p((n + m)

+ n + m) + 2(n + m)

+ 2(n + m)

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

трех универсальных машин, указанных в разделе 3.3:

m n p N

7 4 26 705716

5 5 29 492290

4 6 22 222220

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

Эти цифры несомненно лежат вне пределов досягаемости при

любой практической попытке реализации такой уни версал ьной

µH-системы. Отметим, однако, что при доказательстве упомя-

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

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

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

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

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

блемой. Для этой цели требуется прямое построен ие, миную-

щее обращение к грамматикам и машинам Тьюринга.

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

Расширенные H-системы с разрешающими или запрещающими

контекстными условиями введены в [95], но ограниченные виды

операции сплетения впервые рассматривались в [257], где ис-

следованы, правда, лишь неитеративные операции. Такие опе-

рации сплетения в соответствии с бесконечными (регулярны-

ми) множествами правил изучались в [160]. В основе разде-

ла 8.2 использована раб ота [95]; часть результатов представле-

на также и в [53].

Лемма 8.4 взята из [37], где было высказано предположение,

что H-системы с разрешающим контекстом радиуса 1 и с од-

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

, C

) одно

из множеств C

или C

пусто) характеризуют линейные язы-

ки. Эта гипотеза опровергнута в [250], где доказано, что систе-

мы с пустыми мн ожествами C

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

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

контекстами при небольших радиусах изучены в [230] и [233]:

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

как четверка (|u

|, |u

|); вес системы γ — это четверка

, n

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

ответствующих компонент в весах правил из γ. В рамках этого

подхода в [233] для локальных мишеней усилена теорема 8.4,

а именно, показано, что RE = EH

([1], lt[1]). Этот результат

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

8.8. Комментарии к библиографии 397

монстрирует большие возможности контроля при помощи ло-

кальных языков-мишеней.

Операции сплетения с языками-мишенями рассматривают-

ся в [257]. Раздел 8.3 основан на статье [247]. Программируемые

и развертывающиеся H-системы изучаются в [259], а H-систе-

мы с двойным сплетением были введены в [252].

Мультимножества впервые применены в [73], где с их по-

мощью порождаются нерекурсивные языки. В [240] рекурсив-

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

мов, отображающих языки из EH

(µF IN, F IN). В [95] этот

результат был улучшен и приобрел вид приведенной нами тео-

ремы 8.8. Раздел 8.7 также основан на [95].

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

ложены в [9] (c бесконечными регулярными множествами пра-

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

версальности) и в [94] (с мультимножествами; конструкция ис-

пользует машину Минского из U T M(7, 4) и вариант конструк-

ции из л еммы 8.10). В [94] построена — с по мощью компью-

терной программы — универсальная µH-система с 56 типами

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

три переменные, пробегающие пятиэлементные области. Таким

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

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

В [87] сделана другая попытка явного построения универ-

сальной H-системы, снова с мультимножествами. Результатом

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

шающим 17n

+225n+784, и числом правил сплетения, не пре-

вышающим 29n

+ 405n + 1414, где n — мощность терминаль-

ного алфавита. Эти оценки сопоставимы с оценками из [94].

Глава 9

Сплетение циклических строк

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

терий, молекулы ДНК имеют вид кольцевой последователь-

ности. Поэтому можно рассмотреть общую ситуацию, когда

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

ДНК. Рекомбинация в результате реакции сшивки будет проис-

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

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

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

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

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

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

строки вместе.

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

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

дущих глав. Однако такой подход позволит значительно упро-

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

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

броски и имитации, переброска больше не потребуется.

9.1 Варианты операции сплетения для

циклических строк

Рассмотрим алфавит V . Циклическая строка над V — это по-

следовательность x = a

. . . a

при a

∈ V , 1 6 i 6 n, в

предположении, что a

следует за a

. Другими словами, x мож-

но представить любой циклической перестановкой слова a

. . . a

, например, a

i+1

. . . a

, для произвольного 1 6 i 6

n − 1. Таким образом, циклическая строка над V — это класс

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

циклической перестановки. Обозначим через ˆx циклическую

9.1. Варианты операции сплетения 399

строку, соответствующую линейной строке x ∈ V

∗

, а через



— множество всех циклических строк над V . Любое под-

множество V



назовем циклическим языком.

С каждым обычным языком L ⊆ V

∗

можно связать ц икл и-

ческий язык Cir(L) = {ˆx | x ∈ L}. (В случае одноэлементных

языков будем писать Cir(x) = ˆx.) И наоборот, каждому цикли-

ческому языку L ⊆ V



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

цию Lin(L) = {x | ˆx ∈ L}. Язык L

⊆ V

∗

называется линеари-

зацией циклического языка L

⊆ V



, если Cir(L

) = L

Имея семейство языков F L, можно построить его цикличе-

ский аналог, F L



= {Cir(L) | L ∈ F L}. Таким образом, можно

говорить о F IN



, REG



, RE



и так далее.

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

рации объединения, пересечения, пересечения с регулярными

циклическими языками, прямые и обратные морфизмы, но не

операции произведения или замыкания Клини.

Лемма 9.1. Если FL — семейство языков, замкнутое относи-

тельно циклической перестановки, то L ∈ F L



тогда и толь-

ко тогда, когда Lin(L) ∈ F L.

Доказательство. Обозначим через cp(L) множество всех цик-

лических перестановок строк из L. Ясно, что Lin(Cir(L)) =

cp(L) для любого языка L. Теперь, если L

∈ F L



, то по опре-

делению F L



имеем L

= Cir(L) для некоторого L ∈ F L. По-

скольку Lin(L

) = Lin(Cir(L)) = cp(L), а F L замкнуто отно-

сительно циклической перестановки, получаем Lin(L

) ∈ F L.

Обратно, если L ⊆ V



таков, что Lin(L) ∈ F L, то в силу равен-

ства L = Cir(Lin(L)), имеем L ∈ F L



Следствие 9.1. Пусть FL — семейство языков, замкнутое

относительно циклической перестановки. Тогда, если FL за-

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

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

и F L



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

морфизмов, обратных морфизмов, пересечения с регулярными

циклическими я зыка ми соответственно.

400 9. Сплетение циклических строк

Заметим, что все семейства FIN, REG, CF, CS, RE замкну-

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

LIN не замкнуто: множество cp({a

| n > 1}) ∩ a

n+m

| n, m > 1} не является линейным языком.

Определим теперь для циклических строк некоторые есте-

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

Рассмотрим алфавит V и правило сплетения

r = u

над V . Для ˆx, ˆy, ˆz ∈ V



и v, w ∈ V

∗

, запишем:

(ˆx, ˆy) |=

ˆz тогда и только тогда, когда x = x

, y = y

z = x

при некоторых x

, y

∈ V

∗

ˆx |=

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

, y =

, z = x

при некоторых x

, x

∈ V

∗

(ˆx, v) |=

w тогда и только тогда, когда x = x

, v =

, w = v

при некоторых x

, v

∈ V

∗

v |=

(ˆx, w) тогда и только тогда, когда v = v

x = u

, w = v

при некоторых v

, v

∈ V

∗

В случае |=

две циклически е строки разрезаются в сайтах

, u

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

новую циклическую строку. В случае |=

из одной циклич еской

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

зается в двух сайтах u

, u

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

двух получа ющихся фрагментов. Операция |=

разрезает ц ик-

лическую строку в сайте u

, линейную — в сайте u

, затем

линейная строка, полученная в результате разрезания цикли-

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

разделена линейная строка. Короче говоря, определенная ли-

неаризация циклической строки вставляется внутрь линейной

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

нец, с помощью |=

мы переходим от одной линейной строки,

разрезаемой в двух сайтах u

и u

, к циклической и линей-

ной стр окам. Рис. 9.1 иллюстрирует эти варианты. Еще один

будет рассмотрен в следующем разделе.