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

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

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

∪ {s

1,p

| p

∈ P

}

∪ {r

1,α

| α ∈ N ∪ T ∪ {B}}

∪ {t

} для p ∈ P

1,p

) = {s

2,p

) = {s

| p

∈ P

}

∪ {s

1,p

| p

∈ P

}

∪ {r

1,α

| α ∈ N ∪ T ∪ {B}}

∪ {t

} для p ∈ P

1,α

) = {r

2,α

) = {s

| p ∈ P

}

∪ {s

1,p

| p ∈ P

}

∪ {r

1,β

| β ∈ N ∪ T ∪ {B}}

∪ {t

} для α ∈ N ∪ T ∪ {B},

) = {t

) = ∅.

Отображение регулирует работу γ так, что н ачав имита-

цию правила p ∈ P

(т.е. применив правило сплетения s

1,p

мы должны будем продолжить правилом s

2,p

, а после удале-

ния символа α с правого конца w строки XwY — ввести α с

левого конца w.

Поскольку правилами r

2,α

, α ∈ N ∪ T ∪ {B}, и t

нельзя

воспользоваться в присутствии X

, а X

можно удалить только

с помощью правила s

, применять которое разрешено лишь

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

. Это предотвращает

старт с правил r

2,α

, при котором возникают незаконные строки.

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

точности отвечает выводу в G. Отсюда L(G) = L(γ).

Элегантное с математической точки зрения понятие про-

граммируемой H-системы содержит небиохимический компо-

нент — отображение , определенное независимо от текущих

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

жество доступных правил сплетения меняется на новые пра-

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

вила. Для развертывающихся H-систем, деятельность которых

обусловлена двумя отображениями String и Rule, мы будем ис-

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

гу. Один из возможных подходов — использование точечных

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

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

рассмотрим контекстно -зависимые операции, в которых встав-

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

Для этого, как и в главе 6, вводятся правила вида (u, α/β, v) со

строками u, v и символами α, β или λ. Подобное правило озна-

чает, что символ α может быть заменен на β в контексте (u, v);

α/λ означает удаление, λ/β — вставку, a/b — замену a на b.

Ниже мы увидим (что ожидаемо в свете результа тов главы 6),

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

дим общее определение, в котором фигурируют и замены.

Расширенная H-система с локально развертывающимися

правилами сплетения — это структура

γ = (V, T, A

, A

, E, C

, P ),

где

(i) V — совокупный алфавит γ,

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

(iii) A

⊆ V

∗

— конечное множество начальных аксиом,

(iv) A

⊆ V

∗

— конечное множество текущих аксиом,

(v) E — алфавит, E ∩ V 6= ∅,

(vi) C

— первоначальная последовательность правил сплете-

ния, C

= (r

, . . . , r

), r

∈ E

∗

, 1 6 i 6 k,

(vii) P — конечное множество редактирующих п рави л вида

(u, α/β, v), с u, v ∈ (E ∪ {#, $})

∗

, и α, β ∈ E ∪ {λ}, α 6= β.

Правила из P используются для редактирования правил

сплетения, начиная с «шаблонных» правил из C

. Если α ∈ E,

β ∈ E, перед нами — п одстановка, если α ∈ E, β = λ — удале-

ние, а если α = λ, β ∈ E — вставка. Заметим, что специальные

символы #, $ не редактируются.

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

Идея состоит в том, чтобы использовать компоненты E, C

P для производства правил сплетения. Мы переходим от одно-

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

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

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

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

щем шаге (пер воначально к строке из A

) и к текущей аксио-

ме (строке из A

), то оно должно быть использовано. Иным

способом строки в пробирке изменены быть не могут. После

применения правила сплетения к паре строк все экземпляры

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

не фигурируют на следующих шагах. Исключение составляют

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

мыми (их новые копии добавляются по мере необходимости).

Формализация приводит к следующему определению.

Обозначим через =⇒

обычное отношение вывода в соот-

ветствии с правилами из P , представленными как переписы-

вающие правила uαv → uβv при (u, α/β, v) ∈ P . Для правила

сплетения r ∈ E

∗

мы определим

P (r) = {r

| r =⇒

Распространим отношение =⇒

на k-кортежи правил сплете-

ния следующим образом:

, . . . , r

) =⇒

, . . . , r

)

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

∈ P (r

), 1 6 j 6 k. Начав с

, мы сможем таким путем п олучи ть в момент времени i > 1

последовательность C

= (r

i,1

, . . . , r

i,k

); мы свяжем с ней мно-

жество правил сплетения

= {r | r = r

i,j

при некотором 1 6 j 6 k}.

Заметим, что мн ожество R

содержит в точности одного по-

томка каждого правила из C

; из нескольких вариантов, воз-

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

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

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

Рассмотрим теперь «эволюцию геномов». Определим мно-

жества A

, i > 0, следующим образо м. Первоначальное множе-

ство A

задано.

Для x ∈ V

∗

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

i > 0 оп редел им

(x, R) = 1, если существуют y ∈ A

∪ A

и r ∈ R, такие, что

(x, y)|=

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

(w, z) при некоторых w, z ∈ V

∗

(x, R) = 0 в противном случае.

Кроме того, определим

) = {w ∈ V

∗

|(x, y) |=

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

(z, w)

для r ∈ R

, x, y ∈ A

∪ A

, {x, y} ∩ A

6= ∅}, i > 0.

Тогда

= {x ∈ A

i−1

| δ

i−1

(x, R

i−1

) = 0} ∪ R

i−1

), i > 1.

(Как и в начале этого раздела, можно сказать, что R

Rule(R

i−1

, A

i−1

) и A

= String(R

i−1

, A

i−1

).)

Другими словами, A

состоит из всех строк из A

i−1

, которые

не могут участвовать в сплетении с др угой строкой из A

i−1

или

по правилу из текущего множества R

i−1

, а также из всех

строк, полученных с помощью таких операций сп летен ия. За-

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

не сохраняется, ее больше не существует в следующем множе-

стве A

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

сплетения не может быть применено к строкам из текущего

множества A

(и к аксиомам из A

), все строки из A

неизме-

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

i+1

= A

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

L(γ) = (

[

i>0

) ∩ T

∗

В главе 6 (теорема 6.2) мы видели, что можно охаракте-

ризовать RE, используя правила вставки вида (u, λ/α, v) при

|u|, |v| 6 2, и правил удаления вида (u, λ/α, v) при |u|, |v| 6 1, и

некотором символе α. Комбинируя этот результат с результа-

том из леммы 7.16 (тщательно перестраивая в соответствии с

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

условиями работы расширенной H-системы с локально развер-

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

зацию RE в новых терминах. При этом способе мы используем

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

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

К счастью, характеризация RE остается верной и для до-

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

мися правилами.

Расширенная H-система с локально развертывающимися

правилами сплетения γ = (V, T, A

, A

, E, C

, P ) называется

ограниченной, если card(A

) = 1, card(C

) = 1.

Таким образом, в каждой момент времени мы имеем ровно

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

Обозначим через EH

(F IN, rle[m]), m > 1, семейство язы-

ков L(γ), порожденных ограниченными локально разверты-

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

больше m, m > 1.

Теорема 8.6. EH

(F IN, rle[4]) = RE.

Доказательство. Мы должны доказать только включение

RE ⊆ EH

(F IN, rle[4]).

Рассмотрим грамматику G = (N, T, S, P

) типа 0 в нормаль-

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

1. AB → CD, для A, B, C, D ∈ N,

2. A → BC, для A, B, C ∈ N,

3. A → a, для A ∈ N, a ∈ T ,

4. A → λ, для A ∈ N.

Как обычно, считаем, что правила из P

пронумерованы.

Построим ограниченную расширенную H-систему с локаль-

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

γ = (V, T, A

, A

, E, C

, P ),

где

1. V = N ∪ T ∪ {X, Y, Z, B

2. A

= {XB

SY },

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

3. A

= {ZY }∪{ZvY | u → v ∈ P

}∪{XαZ | α ∈ N ∪T ∪{B

}},

4. E = N ∪ T ∪ {X, Y, Z , B

, c

, d

, e

, f

, g

, h

} ∪ {[r, 1], [r, 2] | r ∈ P

5. C

= (c

#Y $Z#),

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

ных мутаций; чтобы проверить правильность построения, мы

представляем эти правила вместе с текущим конфигурацион-

ным множеством R

, состоящим ровно из одного правила спле-

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

нированно).

1. Производство правил сплетения для имитации переписы-

вающих правил из P

A. Для каждого правила r : AB → CD ∈ P

мы рассматри-

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

0. − − − − − −− c

#Y $Z#,

1. (c

#, λ/[r, 1], Y ), c

#[r, 1]Y $Z#,

2. (λ, c

/λ, #[r, 1]), #[r, 1]Y $Z#,

3. (#, λ/A, [r, 1]), #A[r, 1]Y $Z#,

4. (#A, λ/B, [r, 1]), #AB[r, 1]Y $Z#,

5. (AB[r, 1]Y $Z#, λ/[r, 2], λ), #AB[r, 1]Y $Z#[r, 2],

6. (λ, [r, 1]/λ, Y $Z#[r, 2]), #ABY $Z#[r, 2],

7. (#, λ/C, [r, 2]), #ABY $Z#C[r, 2],

8. (#C, λ/D, [r, 2]), #ABY $Z#CD[r, 2],

9. (CD, λ/Y, [r, 2]), #ABY $Z#CDY [r, 2],

10. (Y, [r, 2]/λ, λ), #ABY $Z#CDY.

Полученное правило сплетения — первое в вышеуказанной по-

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

вида XwY и к аксиомам из A

(символы c

, [r, 1], [r, 2] не по-

являются в V , а значит, и в строках, производимых из A

). Заметим, что правило в ставки 5 можно повторять, вводя

несколько экземпляров символа [r, 2], и, следовательно, произ-

водя строки вида #AB[r, 1]Y $#[r, 2]

при k > 2, но символы

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

C, D и Y будут присутствовать лишь перед самым левым сим-

волом [r, 2]; затем при наличии Y все символы [r, 2] удаляются

(в противном случае получаемое текущее правило сплетения

не может быть использовано).

B. Для каждого правила r : A → BC ∈ P

мы рассматри-

ваем следующие правила мутаций:

0. − − − − − −− c

#Y $Z#,

1. (c

#, λ/[r, 1], Y ), c

#[r, 1]Y $Z#,

2. (λ, c

/λ, #[r, 1]), #[r, 1]Y $Z#,

3. (#, λ/A, [r, 1]), #A[r, 1]Y $Z#,

4. (A[r, 1]Y $Z#, λ/[r, 2], λ), #A[r, 1]Y $Z#[r, 2],

5. (λ, [r, 1]/λ, Y $Z#[r, 2]), #AY $Z#[r, 2],

6. (#, λ/B, [r, 2]), #AY $Z#B[r, 2],

7. (#B, λ/C, [r, 2]), #AY $Z#BC[r, 2],

8. (BC, λ/Y, [r, 2]), #AY $Z#BCY [r, 2],

9. (Y, [r, 2]/λ, λ), #AY $Z#BCY.

C. Любому правилу вида r : A → a ∈ P

мы сопоставляем

правила мутаций 1–5 из группы B, а также следующие три

правила вставки-удаления:

6. (#, λ/a, [r, 2]), #AY $Z#a[r, 2],

7. (a, λ/Y, [r, 2]), #AY $Z#aY [r, 2],

8. (Y, [r, 2]/λ, λ), #AY $Z#aY.

D. Наконец, для любого правила r : A → λ ∈ P

мы вводим

правила 1–5 из группы B, дополняя их такими правилами:

6. (#, λ/Y, [r, 2]), #AY $Z#Y [r, 2],

7. (Y, [r, 2]/λ, λ), #AY $Z#Y.

Во всех случаях только на последнем шаге (после использо-

вания правила B9, C8 или D7 соответственно) мы можем полу-

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

, [r, 1], [r, 2] и, след овател ьно, применимое к строкам, получа-

емых путем сплетения из A

, A

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

Вообще, обозначим соответствующее пра вил о из P

через

u → v. Полученное правило сплетения — #uY $Z#vY , след о-

вательно, можно выполнить сплетение

(Xw|uY, Z|vY ) |= (XwvY, ZuY ).

Строка XwvY — результат имитации правила u → v — бу-

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

ней правило сплетения. При использовании ZuY терминаль-

ная строка не возникнет никогда из-за невозможности устра-

нить символ Z (мы увидим это ниже).

После применения правила #uY $Z#vY мы, продолжив его

редактирование, вернемся к шаблонному правилу c

#Y $Z#.

Это делается благодаря и споль зовани ю следующих правил то-

чечных мутаций:

. 0. − − − − − −− #ABY $Z#CDY,

1. ($Z#CD, λ/e

, )Y, #ABY $Z#CDe

2. (e

, Y/λ, λ), #ABY $Z#CDe

3. (λ, α/λ, e

), #ABY $Z#e

, α ∈ N ∪ T,

4. (λ, λ/e

, Y $Z#e

), #ABe

Y $Z#e

5. (e

Y $Z#, e

/λ, λ), #ABe

Y $Z#,

6. (λ, α/λ, e

), #e

Y $Z#, α ∈ N,

7. (λ, λ/c

, #e

), c

Y $Z#,

8. (c

#, e

/λ, λ), c

#Y $Z#.

Мы вернулись к правилу сплетения из C

. То же самое без

изменений произойдет и в случае B (с CD, стоящим справа

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

, и правилом 6, применяемым

лишь однажды). Для случая C нужно заменить правило 1 на

. ($Z#a, λ/e

, Y ), #AY $Z#ae

а в случае D — на

. ($Z#, λ/e

, Y ), #AY $Z#e

Последующие правила мутаций 2–8 везде действуют одина-

ково, производя правило сплетения c

#Y $Z#; ни одно проме-

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

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

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

из-за управляющих символов e

, e

2. Производство правил сплетения для переброски в текущей

строке:

E. Для каждого символа α ∈ N ∪ T ∪ {B

} мы рассматрива-

ем следующие правила мутаций (создаем правило сплетения,

отрезающее символ α с правого конца строки):

0. − − − − − −− c

#Y $Z#,

1. (c

#, λ/d

, Y ), c

Y $Z#,

2. (λ, c

/λ, #d

), #d

Y $Z#,

3. (#, λ/α, d

), #αd

Y $Z#,

4. (αd

Y $Z#, λ/c

, λ), #αd

Y $Z#c

5. (λ, d

/λ, Y $Z#c

), #αY $Z#c

6. (#, λ/Y, c

), #αY $Z#Y c

7. (Y, c

/λ, λ), #αY $Z#Y.

Полученное правило сплетения не содержит ни одного ре-

гулирующего символа c

, d

, c

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

пользовано для отсечения α с правого конца текущей строки:

(Xw|αY, Z|Y ) |= (XwY, ZαY ).

Строка XwY вступит в соединение на первом же шаге, как

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

же время ZαY никогда не приведет к терминальной строке.

F. Для каждого символа α ∈ N ∪ T ∪ {B

} мы рассмотрим

также следующие правила мутаций (создаем правило сплете-

ния, вписывающее символ α с левого конца данной строки):

0. − − − − − −− #αY $Z#Y,

1. (Z, λ/d

, #Y ), #αY $Zd

#Y,

2. (d

#, Y/λ, λ), #αY $Zd

3. (λ, Z/λ, d

), #αY $d

4. (λ, λ/d

, Y $d

), #αd

Y $d

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

5. (d

Y $, λ/X, d

), #αd

Y $Xd

6. ($X, d

/λ, λ), #αd

Y $X#,

7. (d

Y, λ/Z, $), #αd

Y Z$X#,

8. (d

, Y/λ, Z$), #αd

Z$X#,

9. (λ, λ/X , #αd

), X#αd

Z$X#,

10. (X, λ/α, #αd

), Xα#αd

Z$X#,

11. (Xα#, α/λ, d

), Xα#d

Z$X#,

12. (Xα#, d

/λ, Z), Xα#Z$X#.

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

(Xα|Z, X|wY ) |= (XαwY, XZ),

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

вол. (Заметим, что при таком способе работы γ, трансформи-

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

даемся в регулирующих символах типа X

, Y

, α ∈ N ∪T ∪{B

}

из доказательства леммы 8.2.)

G. (Возврат к шаблонному правилу сплетения c

#Y $Z#;

здесь α ∈ N ∪ T ∪ {B

}):

0. − − − − − −− Xα#Z$X#,

1. (α#Z$, λ/f

, λ), Xα#Z$f

X#,

2. (f

, X/λ, #), Xα#Z$f

3. (f

, λ/Z, #), Xα #Z$f

Z#,

4. (Z, λ/f

, $f

Z), Xα#Zf

Z#,

5. (f

$, f

/λ, λ), Xα#Zf

$Z#,

6. (#, Z/λ, f

), Xα#f

$Z#,

7. (#f

, λ/Y, $), Xα#f

Y $Z#,

8. (λ, λ/c

, Xα#f

Y ), c

Xα#f

Y $Z#,

9. (c

X , α/λ, #f

), c

X#f

Y $Z#,

10. (c

, X/λ, #f

), c

Y $Z#,

11. (c

#, f

/λ, λ), c

#Y $Z#.