2. Грамматики, машины тьюринга и перечислимые языки

Контекстно-свободные грамматики недостаточно «сильны» в смысле порождающей способности, чтобы учесть все синтаксические правила языка программирования (так, все встречающиеся переменные должны быть объявлены) или чтобы вычислить относительно простые функции (например, { | n  }). Поэтому как обобщение контекстно-свободных грамматик введем грамматику Ван-Вайнгаардена.

Грамматика Ван-Вайнгаардена есть шестерка G = (V_Z, V_M, , R, P, S), причем

1. V_Z – алфавит, называемый алфавитом синтаксических знаков, кото­рый не содержит <, >;

2. V_M – конечное множество (которое может быть и пустым), называе­мое множеством метапонятий, где V_M  (V_Z  {<, >}) =  и V = V_M  V_Z;

3.   алфавит, называемый алфавитом базовых или терминальных символов, такой что V_M   = ;

4. R  V_M  V^  конечное множество метапродукций;

5. P  <V^>  (<V^>  )^  конечное множество схем продукций;

6. S  <>  стартовая переменная.

Пусть G = (V_Z, V_M, , R, P, S)  грамматика Ван-Вайнгаардена. Тогда назовем G_A = (V_M, V_Z, R, A)  грамматикой, ассоциированной с метапоня­тием A  V_M. Грамматика G_A  контекстно-свободная и порождает контек­стно-свободный язык L(G_A)  . Из схем продукций получают с помо­щью контекстно-свободного языка L(G_A), A  V_M, продукции, которые по­том применимы в выводах. Чтобы из некоторой схемы продукции полу­чить продукцию, следует все встречающиеся метапонятия согласованно заменить словами из языка L(G_A). Это значит, что если некоторое метапо­нятие A встречается многократно, то все встречаемые A должны быть за­менены одним и тем же словом из L(G_A).

Как ранее, будем писать для (<>, ₁), …,(<>, _n)  P также <>::= ₁ | … | _n и для (A, ₁), …,(A, _n)  R также A::= ₁ | … | _n.

Гомоморфизм h: (V    {<, >})^  (V_Z    {<, >})^ называется до­пустимым (в отношении грамматики G) тогда и только тогда, когда h(a) = a, a  V_Z    {<, >}, h(А)  L(G_A), A  V_M.

Множество продукций определяется следующим образом:

= {<h()>  h() | <>::=   P,   V^,   (<V^>  )^, h – допустимый гомоморфизм}.

(Для различения метапродукций от схем продукций будем записывать продукции в виде: <>  .)

С помощью множеств продукций определяется прямое отношение вы­вода _G (или просто ) над (<>  )^:

 _G    = <>,  = , <>   , ,   (<>  )^.

С помощью L(G) снова обозначим язык, порожденный грамматикой G:

L(G) = {w  ^ | S ^ w}.

При этом ^ есть рефлексивное и транзитивное замыкание отношения  и называется отношением вывода.

Формальный язык L  ^ называется перечислимым, если существует грамматика Ван-Вайнгаардена, такая что L = L(G).

Предложение 2.1. Любой контекстно-свободный язык перечислим.

Доказательство. Пусть <w_i>::= _i1 | … | , 1  i  n, – продукции контек­стно-свободной грамматики G, записанные в нормальной форме Бэкуса, <w₁>  начальная переменная G, V_Z  алфавит с w_i  , 1  i  n и   тер­миналь­ный алфавит. Тогда грамматика Ван-Вайнгаардена G = (V_Z, , , , P, <w₁>), причем P точно содержит продукции в нормаль­ной форме Бэкуса в G, порождает тот же самый язык. □

Чтобы избежать повторов в примерах, условимся о следующем.

Пусть G = (V_Z, V_M, , R, P, S)  грамматика Ван-Вайнгаардена. Все встре­чающиеся большие буквы есть метапонятия в V_M, все встречающиеся малень­кие буквы и специальные знаки есть синтаксические знаки в V_Z или терми­нальные символы в , S обозначается как <начало>. Тем самым должны быть только заданы множества R и P. Теперь с помощью приме­ров покажем, как определенные синтаксические конструкции языков (язы­ков программирова­ния) могут быть представлены с помощью грамматики Ван-Вайнгаардена, со­ответственно как с помощью этой грамматики могут быть вычислены функ­ции. Контекстно-свободные грамматики для этого слишком слабы.

Пример 2.1. Пусть L = {b … bd … d | i_k  i_l, i_k  1 для 1  k, l  n, k  l, j_s  {i_k | 1  k  n}, 1  s  m, m, n  1}. Слова aⁱ могут пони­маться как обозначения переменных в блоке объявления переменных, слова b  как разделительные знаки и d  как правые части присваиваний. Таким образом, L содержит в точности те «куски» программы, в которых все объявленные переменные различно обозначены и в которых объявлены все переменные, встречающиеся в левой части присваивания.

Метапродукции в R заданы посредством:

K::= aK | a, K₁::= K | , K₂::= K | , L::= KbL | Kb, L₁::= L | , L₂::= L | .

Схемы продукций в P заданы посредством:

<начало>::= <L> <проверить L> <применить L>,

<KbL>::= <K> b <L>, <Kb>::= <K> b, <aK>::= a<K>,

<a>::= a,

<проверить KbL>::= <K не лежит в L> <проверить L>,

<проверить Kb>::= ,

<K₁ не лежит в K₂bL>::= <K₁ не равно K₂> <K₁ не лежит в L>,

<K₁ не лежит в K₂b>::= <K₁ не равно K₂>,

<K₁K не равно K₁>::= ,

<K₁ не равно K₁K>::= ,

<применить L₁KbL₂>::= <K> d <применить L₁KbL₂> | <K> d.

Получим:

L(G_k) = {aⁱ | i  1}, L(G_L) = {b … b | i_k  1, 1  k  n, n  1}.

Зададим некоторые продукции в :

<начало>  <a²bab> <проверить a²bab> <применить a²bab> по­этому L ^ a²bab (в G_L);

<проверить a²bab>  <a² не лежит в ab> <проверить ab>, поэтому K ^ a², L ^ ab (в G_K, G_L);

<a² не лежит в ab>  <a² не равно a>, поэтому K₁ ^ a², K₂ ^ a;

<a² не равно a>  , поэтому K₁ ^ a, K ^ a;

<применить a²bab>  <a²> d <применить a²bab>, поэтому L₁ ^ , K ^ a², L₂ ^ ab;

<применить a²bab>  <a²> d, поэтому L₁ ^ , K^ a², L₂ ^ ab.

Слово a²baba²dada²d выводится следующим образом (в G):

<начало>  <aabab> <проверить aabab> <применить aabab>

^ aabab <проверить aabab> <применить aabab> aаbab <aa не лежит в ab> <проверить ab> <применить aabab>

^ aabab <проверить ab> <применить aabab>  aabab <при­менить aabab>

^ aababaad <применить aabab>  aababaad <a> d <приме­нить aabab>

 aababaadad <применить aabab> ^ aababaadadaad. □

Каждому выводу в грамматике Ван-Вайнгаардена G = (V_Z, V_M, , R, P, S) можно сопоставить направленное дерево, узлы которого маркированы с помощью элементов из множества <>  .

1. Выводу S  A₁…A_n, A_i  <>   соответствует дерево вывода (1) на странице 7.

2. Пусть выводу S ^ ₁A₂, ₁, ₂  (<>  )^, A  <> соответст­вует первое дерево вывода (2) на странице 7. Тогда вы­воду S ^ ₁A₂  ₁A₁ … A_n₂, A_i  <>   соответствует вто­рое дерево вывода (2) на странице 8.

Как и ранее, получают результат дерева вывода.

Пример 2.2. Выводу в примере 2.1 соответствует дерево вывода:

<начало>

<a²bab>

<проверить a²bab>

<применить a²bab>

<a²>

b

<ab>

<a² не лежит в ab>

<проверить ab>

<a² > d <применить a²bab>

a

<a> d <применить a²bab>

<a>

<a>

b

<a² не равно a>



a

<a>

a

a



a

a

<a²>

d

a

<a>

a

□

Пример 2.3. Функция Аккерманна f:      определяется следую­щим образом:

Справедливо следующее:

f(1, 1) = f(0, f(1, 0)) = f(0, f(0, 1)) = f(0, 2) = 3.

Мы хотим «вычислить» функцию Аккерманна посредством некоторой грамматики Ван-Вайнгаардена G, то есть должно выполняться:

L(G) = {1^m1ⁿ1^{f(m, n)} | n, m  0}.

(Число n представляется в виде 1^n.)

Метапродукции в R заданы посредством:

M::= M1 | , N::= M, S::= Sf (N, | , T::=) T | .

Схемы продукции в P заданы посредством:

<начало>::= <M><N><f(M, N)>,

<Sf(, N)T>::= <SN1T>, <Sf(M1,)T>::= <Sf(M, 1)T>,

<Sf(M1, N1)T>::= <Sf(M, f(M1, N))T>,

<N1>::= <N>1, <>::= .

Слово 11111 выводится следующим образом:

<начало>  <1><1><f(1, 1)> ^ 11<f(1, 1)>

 11<f(, f(1,))>  11<f(, f(, 1))>

 11<f(, 11)>  11<111> ^ 11111. □

Введем теперь грамматики, которые будут рассматриваться как обоб­щение контекстно-свободных грамматик. Грамматика G задана посредст­вом G = (Ф, , P, S), причем:

1. Ф – алфавит, называемый алфавитом переменных (англ. nontermi­nals).

2.  – алфавит, называемый алфавитом терминальных символов (англ. terminals), причем Ф   =  (пустое множество). Посредст­вом V = Ф   обозначается совокупный алфавит.

3. Р – конечное множество продукций или правил замещения (англ. productions) вида   , причем   V⁺ и   V^. Таким образом, Р есть конечное отношение над V^.

4. S  Ф переменная, называемая стартовой переменной (англ. start symbol).

Для отличия от остальных грамматик грамматику G называют также грамматикой Хомского типа 0.

Теперь мы хотим определить, какой формальный язык порождает грамматика. Для этого нам понадобится определение отношения вывода , которое вводится через отношение .

_G есть отношение над V^, определяемое следующим образом:

 _G  тогда и только тогда, когда  = ,  =  и     P.

Как и раньше, говорят:  непосредственно выводит  или:  может быть непосредственно выведено из .

Отношение  есть снова рефлексивная и транзитивная оболочка отно­шения _G. Говорят также:  выводит , или  может быть выведено из . В случае, если ясно какая грамматика имеется в виду, вместо _G и  можно также писать  и ^.

Слово   V^ называется сентенциальной формой, если S ^ . Обо­значим через L(G) формальный язык, который порождается грамматикой G. L(G) есть множество слов

L(G) = {w | w  ^ и S ^ w}.

Это означает то, что L(G) содержит в точности все те сентенциальные формы, которые являются словами над терминальным алфавитом.

Путем введения ограничений на разрешаемые продукции получают так называемую иерархию грамматик по Хомскому.

Пусть G = (Ф, , P, S)  грамматика. Она называется контекстно-зави­симой, или грамматикой Хомского типа 1 тогда и только тогда, когда ка­ждая продукция     P:

1. имеет вид  = ₁A₂, в случае  = ₁₂, A  Ф, ₁₂  V^,   V⁺;

2. имеет вид S  , в случае если S не встречается в правой части про­дукции.

Контекстно-свободные и регулярные грамматики, получаемые из грамматик типа 0 введением ограничений, называются в этой связи грам­матиками типа 2 и типа 3.

Грамматика G называется ограниченной тогда и только тогда, когда для каждого правила продукции     P выполняется: ||  ||, или, если S не встречается в правой части продукции, когда выполняется  = S и  = .

Можно легко показать, что справедливо следующее предложение.

Предложение 2.2. Формальный язык может порождаться контекстно-зависимой грамматикой тогда и только тогда, когда он может порождаться ограниченной грамматикой. □

Формальный язык называется контекстно-зависимым, если найдется контекстно-зависимая грамматика, которая порождает этот язык.

Пример 2.4. Ограниченная грамматика G = ({S, A, B}, {a, b}, P, S), где

P = {S  abc, S  aAbc, Ab  bA, Ac  Bbcc, bB  Bb, aB  aaA, aB  aa}

порождает язык L(G) = {aⁿbⁿcⁿ | n  1}. (Для доказательства следует рас­смотреть сентенциальные формы aⁱAbⁱcⁱ i  1и выводимые из них формы.) Этот язык является также контекстно-зависимым. Можно показать, что L(G) не является контекстно-свободным. □

Справедливо следующее предложение.

Предложение 2.3. Формальный язык порождается грамматикой Ван-Вайнгаардена тогда и только тогда, когда он порождается грамматикой Хомского типа 0. □

Теперь мы хотим определить автоматы, которые принимают перечис­лимые языки. По историческим причинам эти автоматы называются маши­нами Тью­ринга. Машину Тьюринга можно рассматривать как прибор, ко­торый имеет конечное число состояний и в обе стороны потенциально бес­конечную ленту с головкой чтения-записи. Лента разделена на ячейки, в каждой ячейке находит­ся один символ ленты. Почти все ячейки содержат специальный символ ленты, символ пробела е. Головка чтения-записи мо­жет читать и изменять содержи­мое ячейки. Машина Тьюринга стартует в заданном начальном состоянии, причем головка чтения-записи находится над первым (крайним слева) симво­лом входного слова. Один такт машины Тьюринга (в зависимости от состоя­ния и читаемого символа) состоит из следующих действий:

1. прочитанный символ стирается и на его месте записывается новый символ;

2. головка чтения-записи перемещается на одну ячейку влево или вправо;

3. машина Тьюринга переходит в новое состояние.

Машина Тьюринга может применяться для представления некоторой (в общем случае частичной) функции или для акцептирования некоторого формального языка следующим образом:

1. Машина Тьюринга заканчивает свои вычисления с входным сло­вом w. Содержимое ленты по окончании вычисления означает то­гда значение функции от аргумента w, в случае, если представля­ется функция. Если должен акцептироваться язык, то слово w то­гда и только тогда содержится в языке, когда машина Тьюринга находится по окончании вычисления в конечном состоянии.

2. Процесс вычислений на машине Тьюринга не прерывается. Тогда функция для аргумента w не определена. Соответственно, слово w не содержится в языке.

Двусторонняя детерминированная машина Тьюринга T = (Q, , Г, , q₀, F) определяется через:

1. конечное множество состояний Q;

2. входной алфавит ;

3. алфавит символов ленты Г. При этом Г содержит символ пробела е и выполняется:   Г  {e};

4. функция перехода в общем случае лишь частично определенная:

: (Q  F)  Г  Q  Г  {L, R};

5. начальное состояние q₀  Q;

6. множество конечных состояний F  Q.

Вычисление на машине Тьюринга представляется через конфигурации, причем конфигурация (или ситуация) есть элемент из Г^QГ^. (При этом Q, Q  Г =  используется как алфавит). Конфигурация q интуитивно оз­начает, что машина Тьюринга находится в состоянии q, что  есть содер­жимое ленты и что головка чтения-записи читает первый символ слова .

Условимся, что конфигурация q означает то же самое, что и конфи­гурация eⁿqe^m, n, m  0.

Один шаг вычислений машины Тьюринга T представляется отноше­нием  над конфигурациями. Это отношение определяется следующим об­разом через :

1. qA  Bp, если (q, A) = (p, B, R),

2. CqA  pCB, если (q, A) = (p, B, L),

A, B, C  , ,   ^, q  Q  F, p  Q.

(На основе нашего соглашения выполняется:

q  peB, если (q, e) = (p, B, L), q  Bp, если (q, e) = (p, B, R).)

Говорят также, что отношение  прямо переводит одну конфигурацию в другую. Отношение  переводит некоторую конфигурацию в другую.

Конечная конфигурация есть конфигурация qA, такая, что (q, A) не определена. (В случае, если q  F, то qA автоматически конечная кон­фигурация.)

Машина Тьюринга Т останавливается при вводе слова (w₁, …, w_n), w_i  ^, 1  i  n в конечной конфигурации q, когда

q₀w₁ew₂e … ew_n  q.

Пусть h: ^  (  {e})^  гомоморфизм, который определен через h(A) = A, A    {e}, h(e) = . Пусть T  некоторая машина Тьюринга и n  0. n-местная частичная функция f_T,n: (^)ⁿ  ^, которая представля­ется (или вычисляется) машиной T, задается как:

n-местная частичная функция f: (^)ⁿ  ^ называется частично вы­числимой по Тьюрингу, если существует такая машина Тьюринга, что

f_T,n(w₁, …,w_n) = f(w₁, …,w_n),

для всех (w₁, …, w_n)  (^)ⁿ.

Частично вычислимая по Тьюрингу функция называется полностью вычислимой по Тьюрингу, если T останавливается для всех входных слов (w₁, …, w_n)  (^)ⁿ.

Формальный язык L  ^, принимаемый машиной Тьюринга T, опреде­ляется через:

L = {w | q₀w  q, w  ^, q  F, ,   ^}.

Формальный язык над  называется перечислимым по Тьюрингу, если он принимается некоторой машиной Тьюринга. Он называется разреши­мым по Тьюрингу, если он принимается некоторой машиной Тьюринга, ко­торая останавливается для всех входных слов w  ^.

Пример 2.6. Мы хотим построить машину Тьюринга T, которая при­нимает формальный язык {aⁿbⁿcⁿ | n  1}:

T = (Q, , Г, , q₀, F), где

Q = (q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇, q_f),  = {a, b, c},  = (a, b, c, X, e}, F = {q_f};

Функция перехода  определена следующим образом:

(q0, a) = (q1, a, R) (q1, a) = (q1, a, R) (q1, b) = (q2, b, R) (q2, b) = (q2, b, R) (q2, c) = (q3, c, R) (q3, c) = (q3, c, R) (q3, e) = (q4, e, L)	Проверка, выполнено ли w  a+b+c+. Если да, то T переходит в состояние q4. В противном случае T останавли­вается в одном из состояний q0, q1, q2 или q3, не акцептируя слово.
(q4, X) = (q4, X, L) (q4, c) = (q5, X, L)	Головка передвигается налево до символа c. Он заменяется на X.
(q4, e) = (qf, e, R)	При пробеге влево в состоянии q4 на ленте находятся только символы X. T акцептирует слово.
(q5, c) = (q5, c, L) (q5, X) = (q5, X, L) (q5, b) = (q6, X, L)	Головка передвигается дальше налево до символа b, который заменяется на X.
(q6, b) = (q6, b, L) (q6, X) = (q6, X, L) (q6, a) = (q7, X, R)	Головка передвигается дальше до символа a, который заменяется на X.
(q7, X) = (q7, X, R) (q7, b) = (q7, b, R) (q7, c) = (q7, c, R) (q7, e) = (q4, e, L)	Головка возвращается на самый крайний справа символ X, и T снова попадает в состояние q4.

Если в состоянии q₄ будет найден один из символов a или b, то T оста­навливается, не акцептируя слово. Потому что тогда число символов a или b во входном слове больше, чем число символов c. Если в состоянии q₅ или q₆ не будет найдено b или a, то аналогично T останавливается, не акцепти­руя слово, так как тогда число символов c во входном слове больше, чем количество b или a.

Слово w = a³b³c³ принимается следующим образом:

q₀aaabbbccc ^* aaabbbсссq₃  aaabbbccq₄c 

 aaabbbcq₅cX ^* aaabbq₅bccX  aaabq₆bXccX ^*

^* aaq₆abbXccX  aaXq₇bbXccX ^* aaXbbXccq₄X 

 aaXbbXcq₄cX  aaXbbXq₅cXX ^* aaXbq₅bХcXX 

 aaXq₆bXXcXX ^* aq₆aXbXXcXX  aXq₇XbXXcXX ^*

^* aXXbXXcXq₄X ^* aXXbXXq₄cXX  aXXbXq₅XXXX ^*

^* aXXq₅bXXXXX  aXq₆XXXXXXX ^* q₆aXXXXXXXX 

^* Xq₇XXXXXXXX ^* XXXXXXXXq₄X ^* q₄eXXXXXXXXX 

 q_fXXXXXXXXX.

Акцептирование aⁿbⁿcⁿ требует O(n²) шагов. □

Пример 2.7. Построим теперь машину Тьюринга, которая при вводе aⁿ, n  0 вычисляет двоичное представление числа n как слово над {0, 1}:

T = (Q, , Г, , q₀, F),

где Q = (q₀, q₁, q₂, q₃),  = {a},  = (a, 0, 1, e}, F = ;

Функция перехода  определена следующим образом:

(q0, e) = (q2, 0, L)	При вводе  = а0 возвращается 0.
(q0, a) = (q1, a, R) (q1, a) = (q1, a, R) (q1, 0) = (q1, 0, R) (q1, 1) = (q1, 1, R) (q1, e) = (q2, e, L)	Головка передвигается на крайний справа, отличный от е символ. Если этот символ 0 или 1, то вычисление закончено.
(q2, a) = (q3, e, L) (q3, a) = (q3, a, L)	Если это символ а, то он замещается на е, и головка передвигается влево до двоичного числа, стоящего перед группой символов а.
(q3, 0) = (q1, 1, R) (q3, 1) = (q3, 0, L) (q3, e) = (q1, 1, R)	К этому двоичному числу добавля­ется 1.

Двоичное представление числа 6 вычисляется следующим образом:

 q₀aaaaaa ^* aaaaaq₂a  aaaaq₃a ^* q₃eaaaaa 

 1q₁aaaaa ^* 1aaaaq₂a  1aaaq₃a ^* q₃1aaaa 

 q₃e0aaaa  1q₁0aaaa ^* 1q₃0aaa  11q₁aaa ^*

^* 1q₃1aa  q₃10aa  q₃e00aa  1q₁00aa ^*

^* 10q₃0a  101q₁a ^* 10q₃1  1q₃00 

 11q₁0  110q₁  11q₂0.

Вычисление двоичного представления числа n требует O(n²) шагов. Существует «более сложная» машина Тьюринга, которая вычисляет дво­ичное представление за O(n log n) шагов. □

Как модификацию двусторонней детерминированной машины Тью­ринга рассмотрим одностороннюю детерминированную машину Тьюринга. Она имеет ленту, которая потенциально бесконечна только в одну сторону. Конец ленты маркируется некоторым специальным символом, например Z₀, который не должен меняться.

Пусть Т₂ двусторонняя машина Тьюринга. Тогда односторонняя ма­шина Тьюринга Т₁ моделирует двустороннюю машину Тьюринга Т₂ сле­дующим образом. Начальный участок ленты машины Т₁ при необходимо­сти разделяется на две дорожки (т. е. алфавит ленты машины Т₁ содержит Г  Г, где Г – алфавит ленты Т₂). Вторая дорожка служит для того, чтобы представлять содержание ячеек машины Т₂, которые лежат левее той ячейки, над которой находится головка чтения-записи в начале вычисле­ний. В своем множестве состояний Т₁ «отмечает», находится она на верх­ней или на нижней дорожке (т. е. множество состояний машины Т₁ содер­жит Q  {вверху, внизу}, где Q – множество состояний машины Т₂). Если, например, машина Т₂, исходя из начальной конфигурации, q₀a₁a₂a₃a₄a₅ де­лает три шага влево, при которых последовательно записываются символы А₁, А₂, А₃, то достигаемая тем самым конфигурация qeA₃A₂A₁a₂a₃a₄a₅ ма­шины Т₂ представляется с помощью машины Т₁ следующим образом:

Если машина Т₂ выполняет передвижение вправо, то и машина Т₁, если она находится в состоянии (q, вверху), тоже выполняет движение вправо. Если же машина Т₁, как в предыдущем примере, находится в состоянии (q, внизу), то она выполняет движение влево. Подобное справедливо при пе­редвижении машины Т₂ влево. Если Т₁ достигает символа Z₀, то она должна перейти из состояния (q, внизу) в (q, вверху), или наоборот.

В конце вычислений, если должна представляться функция, все сим­волы должны быть сдвинуты на верхнюю дорожку и пары заменяются на А.

В следующем предложении мы сформулируем, что языки, принимае­мые машинами Тьюринга, есть в точности перечислимые языки.

Предложение 2.4. Пусть L  формальный язык. Тогда следующие вы­сказывания эквивалентны:

1. Существует грамматика Ван-Вайнгаардена, которая порождает L.

2. Существует грамматика Хомского типа 0, которая порождает L.

3. Существует двусторонняя детерминированная машина Тью­ринга, которая принимает L.

4. Существует односторонняя детерминированная машина Тью­ринга, которая принимает L.

Доказательство. Мы покажем только моделирование действий одно­сторонней машины Тьюринга T = (Q, , Г, , q₀, F) грамматикой типа 0 G = ({S, T, $}  Q  (  ), , P, S). При этом следующие продукции ле­жат в Р:

1. S  TZ₀q₀, T  $, T  aTa, a  .

Эти продукции осуществляют вывод S ^ w$w^RZ₀q₀, где w  ^.

2. aq  pb для (q, a) = (p, b, R),

aqcbcp для (q, a) = (p, b, L),

$  $e.

Применяя эти продукции, мы можем моделировать действия машины Тьюринга Т: S ^ w$q тогда и только тогда, ко­гда q₀Z₀w ^* ₁q₂.

3. qz  q, zq  q, $q  , q  F, z  .

Если Т достигает конечной конфигурации ₁q₂, q  F, то с по­мощью продукций (i), (ii) возможен вывод: S ^ w$q. С по­мощью продукций (iii) возможен следующий вывод: w$q ^ w. □

Рассмотрим другую модификацию машины Тьюринга – многоленточ­ную машину. Детерминированная k-ленточная машина Тьюринга имеет k лент, потенциально бесконечных в обе стороны. Над каждой лентой нахо­дится головка чтения-записи. Функция перехода  имеет в качестве аргу­ментов соответствующее состояние и символы, читаемые на каждой из лент. Ее значения задают новое состояние, новые символы, которые запи­сываются на месте старых, и независимые друг от друга перемещения го­ловок чтения-записи, которые на каждом шаге передвигаются влево (L), вправо (R) или не передвигаются (S):

(q, A₁, …, A_k) = (p, B₁, …, B_k, S₁, …, S_k),

где q, p  Q, A_i, B_i  , S_i  {L, S, R}.

(Также и в рассматривающихся до сих пор моделях машин Тьюринга воз­можно допустить отсутствие передвижения головки чтения-записи при прямом переходе. Тем самым вычислительная «сила» машины Тьюринга не повышается – только что «программирование» становится удобней.)

Конфигурация k-ленточной машины Тьюринга есть элементы из (Q  (^^)^k. При этом специальный символ  обозначает положение го­ловки чтения-записи на соответствующей ленте. Таким образом, конфигу­рации имеют вид:

(q, ₁₁, ₂₂, …, _k_k).

Входное слово (w₁, …, w_n) представляется конфигурацией (q₀, w₁e … ew_n, , …, ). Переход от одной конфигурации к другой осуще­ствляется детерминированным образом с помощью функций перехода. Ос­тальные определения, которые относятся к машинам Тьюринга, перено­сятся аналогично.

Предложение 2.5. k-ленточная машина Тьюринга (k  1) может быть смоделирована двухсторонней машиной Тьюринга.

Доказательство. Пусть Т – k-ленточная машина Тьюринга. Тогда кон­фигурация машины Т может быть смоделирована двухсторонней машиной Тьюринга Т₁, лента которой разделена на 2k дорожек:

Дорожка «лента i» содержит содержимое i-той ленты машины Т₁, до­рожка «головка i» маркирует позицию i-той дорожки, в которой находится головка чтения-записи машины Т. В состояниях машины Т₁ хранится ин­формация о том, находится символ Х на дорожке «головка i» слева или справа от головки чтения-записи машины Т₁. Кроме того, соответствую­щие состояния машины Т хранятся в машине Т₁. Для моделирования пере­хода машины Т машина Т₁ должна найти символ Х на дорожке «головка i» и лежащий под ним символ на дорожке «лента i» занести как информацию в состояние. После просмотра всех k дорожек машина Т₁ знает, как нужно изменить k символов и как нужно выверить позиции символа Х. Тогда не­обходимо снова найти символ Х на до­рожке «головка i», лежащий под ним символ заменить согласно функции пе­рехода машины Т и сдвинуть при необходимости символ Х. После того как это проделано для всех дорожек, Т₁ находится в конфигурации, которая представ­ляет последовательность конфигураций машины Т. Разумеется, на каждом ша­ге нужно следить за тем, чтобы информация о том, находится символ Х на до­рожке «головка i» слева или справа от головки чтения-записи машины Т₁, была занесена в новое состояние. □

Преимущество многоленточных машин Тьюринга состоит в том, что они в общем случае быстрее, чем одноленточные.

Пример 2.8. Мы хотим построить двухленточную машину Тьюринга, которая принимает формальный язык {aⁿbⁿcⁿ | n  1}:

T = (Q, , Г, , q₀, F),

где Q = (q₀, q₁, q₂, q_f),  = {a, b, c},  = (a, b, c, e}, F = {q_f}.

Функция перехода  определена следующим образом:

(q0, a, e) = (q0, a, a, R, R)	Ведущая а-группа входного слова ко­пируется на вторую ленту.
(q0, b, e) = (q1, b, e, S, L)	Как только на первой ленте появля­ется b, то головка на второй ленте ус­танавливается на последний скопиро­ванный символ а.
(q1, b, a) = (q1, b, a, R, L)	Теперь количество символов b на первой ленте сравнивается с количе­ством символов а на второй ленте.
(q1, с, е) = (q2, с, е, S, R)	Если эти числа совпадают и на пер­вой ленте появляется символ с, то го­ловка на второй ленте устанавлива­ется на первом копируемом символе а.
(q2, с, а) = (q2, с, а, R, R)	Теперь количество символов с на первой ленте сравнивается с количе­ством символов а на второй ленте.
(q2, е, е) = (qf, e, e, S, S)	Если эти числа совпадают, то входное слово принимается.

Слово a³b³c³ принимается следующим образом:

(q₀, aaabbbccc, ) ^* (q₀, aaabbbccc, aaa) 

 (q₁, aaabbbccc, aaa) ^* (q₁, aaabbbccc, eaaa) 

 (q₂, aaabbbccc, aaa) ^* (q₂, aaabbbccc, aaa) 

 (q_f, aaabbbccc, aaa).

Принятие слова aⁿbⁿcⁿ требует О(n) шагов. □

Дальнейшей модификацией машины Тьюринга является недетермини­рованная машина Тьюринга. При этом функция перехода  производит отображение в конечные подмножества состояний символов и изменений направления. Лента в обоих направлениях является потенциально беско­нечной. Здесь нельзя больше говорить о функции, определенной недетер­минированной машиной Тьюринга, так как она была бы определена неод­нозначно. Мы получили бы здесь отношение. Однако недетерминирован­ная машина Тьюринга принимает слово тогда, когда она для какой-либо последовательности прямых переходов останавливается в конечном со­стоянии. Множество принятых слов есть тогда формальный язык, прини­маемый недетерминированной машиной Тьюринга.

Предложение 2.6. Недетерминированная машина Тьюринга может быть смоделирована трехленточной машиной Тьюринга (и тем самым обычной машиной Тьюринга).

Доказательство. Пусть Т  недетерминированная машина Тьюринга. Для каждого состояния и каждого символа ленты существует не более чем конечное число возможностей для прямого перехода. Пусть r максималь­ное число таких возможностей. Следующая трехленточная машина Тью­ринга Т₁ моделирует Т.

Первая лента машины Т₁ содержит входное слово. На второй ленте представляются числа в системе счисления по базису r, упорядоченные по величине. Каждому такому числу может, но не обязательно, соответство­вать одна из возможностей прямых переходов.

Для каждого числа на второй ленте входное слово копируется с первой ленты на третью и машина Т моделируется машиной Т₁ на третьей ленте, в соответствии с числом, записанным на второй ленте. Если Т останавлива­ется в конечном состоянии, то останавливается и Т₁. □

Пример 2.9. Построим недетерминированную машину Тьюринга для проблемы рюкзака (англ. knapsackproblem):

Даны натуральные числа x₁, …, x_m, m  1. Существует ли подмно­жество J  {1, …, m1}, такое, что ?

(Эту проблему можно наглядно сформулировать так: даны какие-либо предметы размером x₁, …, x_m-1. Можно ли рюкзак вместимостью x_m напол­нить полностью путем некоторого выбора этих предметов?)

Представим эту проблему как формальный язык

RUCKSACK = {w₁a … aw_m | w_i, где 1  i  m и m  1, есть двоичное представление натурального числа x_i, и существует подмножество J  {1, …, m1}, такое, что }

и построим недетерминированную машину Тьюринга Т, которая прини­мает этот язык. (Для простоты будем допускать ведущие нули в двоичных числах и разрешим число 0 изображать через .). Машина Тьюринга обра­батывает последовательность чисел w₁a … aw_m слева направо. Для каждого символа а она может (недетерминированным образом) стоящее слева от а число x_i либо игнорировать (x_i не пакуется в рюкзак), либо вычитать из x_m (x_i пакуется в рюкзак). Входное слово принимается в точности тогда, когда последнее число последовательности сократится до нуля. Вычитание числа x_i из x_m происходит (как при ручных вычислениях) цифра за цифрой. Вы­чтенные уже цифры в x_i заменяются на символ Х; позиция в x_m, в которой только что проводилось вычитание, маркируется (т. е. вместо 0 или 1 пи­шется или ), для того чтобы обеспечить правильность соответствия пози­ций при вычитании. Формально машина Т строится следующим обра­зом:

T = (Q, , Г, , q₀, F),

где Q = (q₀, q₁, q₂, q₃, q₄, q₅, r₀, r₁, s₀, s₁, t₁, q_f),  = {0, 1, a},  = {0, 1, a, X, , , e}, F ={q_f};

функция перехода  определена следующим образом:

(q0, e) = {(qf, e, L)}	Последнее число 0 – входное слово прини­мается.
(q0, 0) = {(q0, e, R)}	Ведущие нули стираются.
(q0, а) = {(q0, e, R)}	xi состоит только из нулей, игнорировать.
(q0, 1) = {(q1, 1, R)} (q1, 0) = {(q1, 0, R)} (q1, 1) = {(q1, 1, R)}	xi содержит 1 – идти направо до следующего символа а.
(q1, а) = {(q0, е, R), (q2, X, L)}	xi игнорировать или вычитать.  недетерминировано!
(q2, Х) = {(q2, Х, L)}	Искать следующую еще не вычтенную цифру.
(q2, 0) = {(r0, Х, R)} (q2, 1) = {(r1, Х, R)}	Заметить вычитаемую цифру.
(q2, е) = {(q3, e, R)}	Завершить вычитание xi.
(q3, X) = {(q3, e, R)}	Все символы Х стереть.
(q3, 0) = {(q3, 0, R)} (q3, 1) = {(q3, 1, R)} (q3, а) = {(q3, а, R)}	Идти вправо до маркировки.
(q3, ) = {(q4, 0, R)} (q3, ) = {(q4, 1, R)}	Удалить маркировку.
(q4, 0) = {(q4, 0, L)} (q4, 1) = {(q4, 1, L)} (q4, a) = {(q4, a, L)} (q4, e) = {(q0, e, R)}	Идти влево к началу xi+1.
(r0, X) = {(r0, X, R)} (r0, 0) = {(r0, 0, R)} (r0, 1) = {(r0, 1, R)} (r0, а) = {(r0, а, R)} (r0, e) = {(s0, e, L)} (r0, ) = {(s0, 0, L)} (r0, ) = {(s0, 1, L)}	(r1, X) = {(r1, X, R)} (r1, 0) = {(r1, 0, R)} (r1, 1) = {(r1, 1, R)} (r1, а) = {(r1, а, R)} (r1, e) = {(s1, e, L)} (r1, ) = {(s1, 0, L)} (r1, ) = {(s1, 1, L)}	Идти вправо до пос­ледней немаркирован­ной цифры, при необ­ходимости удалить старую маркировку.
(s0, 0) = {(q5, , L)} (s0, 1) = {(q5, , L)}	(s1, 0) = {(t1, , L)} (s1, 1) = {(q5, , L)} (t1, 0) = {(t1, 1, L)} (t1, 1) = {(q5, 0, L)}	Произвести вычита­ние 0 (соотв. 1), при этом маркировать воз­никающие цифры. Учи­тывать возможный перенос (t1).
(q5, 0) = {(q5, 0, L)} (q5, 1) = {(q5, 1, L)} (q5, а) = {(q5, а, L)} (q5, Х) = {(q2, Х, L)}	Идти налево до символа Х и снова в cостоя­ние q2, для того чтобы искать следующую вычитаемую цифру.

Проблема рюкзака х₁ = 2, х₂ = 3, х₃ = 1, х₄ = 5 может быть решена с по­мощью машины Т (поскольку х₁ + х₂ = х₄) следующим образом:

q₀010a11a01a101 ^* 1q₂0X11a01a101 ^*

^* XXX11a01a1q₅0 ^* XXX11a01q₅a01 ^*

^* q₀11a01a011 ^* XXX01q₅00 ^*

^* q₀01a000 ^* 1eeeq_f. □