1 Глава 7. Машины Тьюринга: проблема остановки, языки типа 0 Теория формальных языков и трансляций

2 § 7.1. Универсальная машина Тьюринга В этой главе мы покажем, что существует машина Тьюринга U, которая по заданному коду произвольной машины Тьюринга T и кодированию входной цепочки x будет моделировать поведение машины T с входной цепочкой x. Такая машина U называется универсальной машиной Тьюринга.

3 Её можно рассматривать как вычисли- тельную машину общего назначения, которая достаточно мощна для того, чтобы моделировать любую вычислительную машину, включая саму себя. Универсальная машина Тьюринга

4 Мы покажем также, что не существует алгоритма (т. е. машины Тьюринга, которая останавливается на всех входных цепочках), который мог бы определить для произвольной машины Тьюринга T и произвольной её входной цепочки x, остановится ли когда-нибудь машина T с входной цепочкой x. Универсальная машина Тьюринга

5 Этот отрицательный результат интенсивно используется как аргумент для того, чтобы показать, что многие проблемы, относящиеся к различным классам языков, являются рекурсивно (т. е. алгоритмически) неразреши- мыми. Универсальная машина Тьюринга

6 Будет также показано, что имеются рекурсивно перечислимые множества, которые не являются рекурсивными. Другими словами, есть множества, которые распознаются машинами Тьюринга, но не такими, которые останавливаются на всех входных цепочках. Универсальная машина Тьюринга

7 Наконец, будет доказана основная теорема об эквивалентности языков типа 0 и множеств, распознаваемых машинами Тьюринга. Универсальная машина Тьюринга

8 Покажем, что универсальная машина Тьюринга существует путём действитель- ного её построения. Прежде всего мы должны условиться относительно кодирования машин Тьюринга и кодирования их входных цепочек. Поскольку машина Тьюринга T 1 может иметь любое число допустимых символов ленты, мы предполагаем, что все они будут кодироваться при помощи символов 0 и 1. Универсальная машина Тьюринга

9 Очевидно, что для каждой Tm T 1 существует Tm T 2 с ленточными символами 0 и 1 и одним дополнительным символом ленты B (пробел), которая принимает точно те строки из множества {0, 1} *, которые являются кодами слов, принимаемых машиной T 1. Универсальная машина Тьюринга

10 Принимая это во внимание, достаточно спроектировать универсальную машину Тьюринга для машин Тьюринга с одина- ковыми ленточными алфавитами {0, 1, B}. Поскольку машина Тьюринга может иметь произвольно большое число состояний и, поскольку мы имеем только фиксированное число допустимых символов ленты, то кодируем состояния в виде 1, 11, 111, и т. д. Универсальная машина Тьюринга

11 Один из способов закодировать таблицу состояний состоит в том, чтобы разметить некоторое число блоков, равное числу состояний, а затем разбить каждый блок на три подблока, соответствующих символам ленты B, 0 и 1. Состоянию i будет соответствовать i-й блок, а три подблока будут относиться к символам B, 0 и 1 соответственно. Универсальная машина Тьюринга

12 Блоки будут отделяться двумя символами c, а подблоки одним символом c. Начало и конец таблицы будет отмечаться тремя символами c. Например, машина Тьюринга с этими тремя допустимыми ленточными символами и четырьмя состояниями может быть пол- ностью определена при помощи табл Универсальная машина Тьюринга

13 Таблица 7.1 Универсальная машина Тьюринга Состояние Входной символ B01 1 2, 0, R 23, 1, L 2, 1, R 34, 0, R 3, 1, L 4 Ret 16Ret 17

14 Если в машине Тьюринга T, которая кодируется, (i, a) = (j, b, D), то под- блок, соответствующий состоянию i и символу ленты a {B, 0, 1}, будет содержать j единиц, за которыми следу- ет символ D {L, R}, а за ним b {0, 1}. Если (i, a) не определено, то соответ- ствующий подблок будет содержать единственный нуль. Универсальная машина Тьюринга

15 Таким образом, кодировка табл. 7.1 оказалась бы такой, как приводимая ниже запись: ссс0с0с11R0сс 111L1c111L1c11R1cc 1111R0c1111R0c111L1cc 0с0с0ссc Код 11R0 в подблоке, соответствующем состоянию 1 и входному символу 1, означает то, что машина T, будучи в состоянии 1 и сканируя символ 1, будет заменять 1 на 0, двигаться вправо и входить в состояние 2. Универсальная машина Тьюринга Блок состояния 1 Блок состояния 2 Блок состояния 3 Блок состояния 4

16 Любое состояние, в котором для всех трёх допустимых символов ленты пере- ходные состояния не определены, интерпретируется как принимающее (или конечное) состояние. Таково состояние 4 в табл Предполагается, что после приёма входной цепочки машина не делает больше никаких движений. Универсальная машина Тьюринга

17 В любом непринимающем состоянии, по крайней мере, для одного допустимого символа ленты следующее состояние должно быть определено. В роли начального состояния всегда используется состояние 1. Хотя мы использовали только пять символов B, 0, 1, L, R, чтобы закодировать машину Тьюринга, показанную в табл. 7.1, универсальная машина Тьюринга будет использовать 12 символов ленты.7.1 Универсальная машина Тьюринга

18 Дополнительные символы появляются из того соображения, что она будет иметь двухдорожечную ленту. Нижняя дорожка будет использовать символы c, 0, 1, L, R и B, в то время как верхняя символы m и B. Теперь неформально опишем универсаль- ную машину Тьюринга (U). Универсальная машина Тьюринга

19 Её лента, как сказано, устроена на двухдорожечной ленте. Нижняя дорожка будет содержать кодировку некоторой машины Тьюринга (T), за которой будет следовать цепочка из нулей и единиц, представляющая её входные данные. Данные отделяются от кодирования машины тремя последовательными с. Универсальная машина Тьюринга

20 Первоначально верхняя дорожка будет вся заполнена символами B (пробелами), за исключением двух ячеек: третьего символа с в цепочке ссс в начале кода машины и первой ячейки данных, которые помечены m. См. ниже: Универсальная машина Тьюринга

21 Универсальная машина Тьюринга ccc блок 1 cc блок 2 cc... cc блок N ссс Универсальная машина Тьюринга U будет моделировать движения, которые бы предпринимала Tm T на входной цепочке, представленной как данные на ленте машины U, следующим образом. данные m m программа

22 [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc U m m 1. Машина U пере- двигает свою головку вправо, пока она не обнаружит маркер в области данных над входным символом, ска- нируемым машиной T. Универсальная машина Тьюринга

23 2. Этот символ, назовем его A, запоминается в конечном управлении ма- шины U, которая с этого момента начинает движе- ние влево, пока не достиг- нет маркера, регистрирую- щего текущее состояние машины T (отмечающего соответствующий блок в коде таблицы машины T). [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc m m Универсальная машина Тьюринга U(1)

24 3. Машина U удаляет этот маркер (заменяет его симво- лом B), передвигается вправо к подблоку, соответствующему символу A (=1), и помещает маркер над первым символом S в этом подблоке при условии, что S = 1. В последующем этот маркер подблока будем называть m 1. Если же S = 0, то машина U останавливается, поскольку у машины T нет никакого следующего движения. [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc m m m1m1 U Универсальная машина Тьюринга 30

25 [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc m U m1m1 m2m2 4. Предположим, что S = 1. Тогда машина U движется влево, пока не находит цепочку ссс. Затем машина U движется вправо, помечая крайнее правое из этих трех с. Этот маркер назовем m 2. Универсальная машина Тьюринга

26 [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc m2m2 m 5. После этого машина U входит в подпрограмму, которая попеременно пе- редвигает маркер m 1 на один символ 1 вправо, а маркер m 2 на один блок вправо. Чтобы различать эти маркеры (т. к. оба есть m) машина U будет запоми- нать в своем конечном управлении: m 2 левее или правее m 1. Универсальная машина Тьюринга m1m1

27 [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc m m1m1 6. Когда машина U сдвигает m 1 на символ, который не является 1, т. е. он есть L или R, маркер m 2 распола- гается над символом с, который как раз перед блоком, соответствующим следующему состоянию машины T. Универсальная машина Тьюринга m2m2 m 2 маркер следующего состояния

28 m 1 [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc m2m2 U(R0) m 7. В этой точке машина U удаляет маркер m 1 и запи- сывает в своем конечном управлении направление (R), в котором машина T будет двигать свою голов- ку ленты, и символ (0), который машина T должна печатать. Затем машина U снова движется вправо в область данных и находит маркер, который указывает место головки ленты машины T. Универсальная машина Тьюринга

29 m U(R0) 8. Символ, находящийся под маркером, заменяется на символ, запомненный в конечном управлении (0), а маркер сдвигается на одну ячейку в направ- лении, также зафиксиро- ванном в конечном управ- лении (R). Таким образом машина U смоделировала одно движение машины T. [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc m2m2 Универсальная машина Тьюринга 0 1

30 Далее машина U запо- минает новый символ (1), сканируемый машиной T, в своем конечном управле- нии, начинает двигаться влево, пока не достигнет маркера m 2, регистрирую- щего текущее состояние машины T, и повторяет процесс, который был только что описан (см. п.3).п.3 Универсальная машина Тьюринга [1] ссс0с0с11R0сс [2]111L1c111L1c11R1cc [3]1111R0c1111R0c111L1cc [4]0с0с0ссc U m2m2 U(1) m

31 Если машина T останавливается с этими конкретными данными, то машина U, в точности воспроизведя все движения машины T, тоже останавливается, а в области данных будет зафиксировано финальное содержание ленты машины T. Универсальная машина Тьюринга

32 Когда машина T останавливается, машина U может сообщить, находится ли машина T в принимающем состоянии или нет. Если машина T не останавливается, то машина U тоже не останавливается, т. е. не принимает. Так универсальная машина Тьюринга моделирует машину Тьюринга T. Универсальная машина Тьюринга

33 Детальное устройство универсальной машины Тьюринга, которую мы описали неформально, дано в Пособии в табл. 7.2 на стр Универсальная машина Тьюринга

34 Табл. 7.2

35

36 Примечание. Элементы таблицы имеют следующие значения. Тройка из состояния, ленточного символа и L или R указывает следующее состояние, символ ленты, который печатать, и направление движения. Пара из состояния и L или R указывает следующее состояние и направление движения, при этом ленточный символ остаётся неизменным. Символы L или R и слова Двигаться влево или Двигаться вправо указывают, что машина Тьюринга движется влево или вправо, не изменяя состояния и символа ленты. Прочерк обозначает ситуацию, которая никогда не случается. Состояние Y является принимающим. Следовательно, никакое движение из состояния Y невозможно.

37 Отметим, что эта универсальная машина Тьюринга имеет 12 ленточных символов, но может моделировать только машину Тьюринга с двумя допустимыми символами ленты. Но можно построить эквивалентную универсальную машину Тьюринга, которая будет использовать только два допустимых символа ленты. Универсальная машина Тьюринга

38 Для этого каждый допустимый символ ленты надо закодировать блоком из четырех символов 0 или 1. Часть первоначальной ленты с данными будет использовать четыре ячейки вместо одной непустой ячейки на оригинальной входной ленте машины T. Универсальная машина Тьюринга

39 § 7.2. Неразрешимость проблемы остановки Проблема остановки машины Тьюринга формулируется следующим образом. Дана машина Тьюринга в произвольной конфигурации со строкой непустых ленточных символов конечной длины. Остановиться ли она в конце концов?

40 Говорят, что эта проблема рекурсивно не разрешима в том смысле, что не существует алгоритма для её решения. Это совсем не значит, что мы не можем определить, остановится ли данная конкретная Tm с данной входной цепочкой. Неразрешимость проблемы остановки

41 При описании универсальной машины Тьюринга мы имели кодирование для любой Tm с ленточными символами 0, 1 и B. Кодированием программы Tm была цепочка из {0, 1, c, L, R} *. Неразрешимость проблемы остановки

42 Мы можем перенумеровать все такие цепочки (т. е. машины Тьюринга), перечис- ляя их в порядке возрастания длины. Цепочки одинаковой длины упорядочива- ются в соответствии со значением строки по основанию 5. Предполагается, что эти 5 символов, упорядоченные каком-нибудь порядке, играют роль цифр 0, 1, 2, 3, 4. Неразрешимость проблемы остановки

43 Аналогичным образом входные цепочки из множества {0, 1} * могут быть тоже упорядочены. Первыми цепочками являются, 0, 1, 00, 01, 10, 11, 000, 001,.... Таким образом, имеет смысл говорить об i-й цепочке в множестве {0, 1} *. Неразрешимость проблемы остановки

44 Если мы предположим, что каждая цепочка из множества {0, 1, c, L, R} * является машиной Тьюринга (некоторые цепочки будут образованы неправильно они рассматриваются как Tm без каких- нибудь движений), то так же имеет смысл говорить о j-й машине Тьюринга, т. е. о машине, представленной j-й цепочкой из множества {0, 1, c, L, R} *. Неразрешимость проблемы остановки

45 Рассмотрим язык L 1 = {x i x i не принимается Tm T i }. Покажем, что язык L 1 не распознаётся никакой Tm. Действительно, если бы это не было так, то существовала бы некоторая машина Тьюринга, скажем T j, которая бы распознавала этот язык, т. е. L 1 = T(T j ). Неразрешимость проблемы остановки

46 Возьмём, цепочку x j. Случай 1. Если x j L 1, то есть x j T(T j ), то по определению языка L 1 должно быть x j L 1. Противоречие! Случай 2. Если x j L 1, то есть x j T(T j ), то по определению языка L 1 должно быть x j L 1. Противоречие! Остается признать, что язык L 1 не распознаётся никакой Tm. Неразрешимость проблемы остановки

47 Обратимся к проблеме остановки. Предположим противное, что мы имели бы алгоритм, т. е. машину Тьюринга T 0, которая всегда останавливается и определяет, остановится ли когда-нибудь любая данная Тьюринга в данной конфигурации. Тогда мы могли бы построить машину Тьюринга T, которая распознаёт язык L 1, а это противоречило бы только что установленному факту, что такой Tm не существует. Неразрешимость проблемы остановки

48 Машина T действовала бы следующим образом: 1. Пусть x * на её входе. Прежде всего она перечисляет цепочки x 1, x 2,... из множества * до тех пор, пока не обнаружит, что некоторое x i = x. Таким образом Tm T определяет, что x является i-м предложением в этом перечислении. Неразрешимость проблемы остановки

49 2. Затем Tm T генерирует код машины Тьюринга T i. 3. Управление теперь передается машине T 0, которая может определить, останавливается Tm T i с входной цепочкой x i или нет. 4. Если установлено, что Tm T i не останавливается с входной цепочкой x i (т. е. Tm T i не принимает x i ), то машина T останавливается и принимает. Неразрешимость проблемы остановки

50 5. Если же установлено, что Tm T i останавливается с входной цепочкой x i, то управление передается универсальной машине Тьюринга U, которая моделирует машину T i с входной цепочкой x i. Неразрешимость проблемы остановки

51 6. Поскольку, как было выяснено на предыдущем шаге, Tm T i останавливается с входной цепочкой x i, то универсальная машина Тьюринга останавливается и определяет, принимает машина T i цепочку x i или нет. В любом случае Tm T останавливается, принимая x i в случае, когда Tm T i цепочку x i не принимает, и наоборот, отвергая её, если Tm T i её принимает. Неразрешимость проблемы остановки

52 Итак, наше предположение о том, что существует машина Тьюринга T 0, которая всегда останавливается и решает проблему остановки произвольной машины Тьюринга, привела нас к противоречию, состоящему в том, что мы сумели построить машину Тьюринга, распознающую язык L 1. Это даёт возможность сформулировать следующее утверждение. Неразрешимость проблемы остановки

53 Теорема 7.1. Не существует алгоритма (т. е. машины Тьюринга, которая гаранти- рованно останавливается) для определения, остановится ли в конце концов произволь- ная машина Тьюринга, начиная движение в произвольно заданной конфигурации. Доказательство вытекает из подходящей формализации вышеприведённого рассуж- дения. Неразрешимость проблемы остановки

54 Для многих проблем не существует разрешающего алгоритма, в частности, для решения некоторых проблем, касающихся формальных языков. Неразрешимость проблемы остановки

55 § 7.3. Класс рекурсивных множеств Мы можем теперь показать, что класс рекурсивных множеств является собствен- ным подмножеством рекурсивно пере- числимых множеств. Другими словами, существует язык, который может быть распознан машиной Тьюринга, которая не останавливается на некоторых предложениях не из этого языка, но не может быть распознан никакой машиной Тьюринга, которая останавли- вается всегда.

56 Примером такого множества является дополнение множества L 1, о котором шла речь в предыдущем параграфе. Прежде, чем утверждать это, докажем две леммы. Класс рекурсивных множеств

57 Лемма 7.1. Если множество рекурсивно, то его дополнение рекурсивно. Доказательство. Если L рекур- сивное множество, то существует машина Тьюринга T, гарантированно останавливаю- щаяся, которая распознаёт язык L. Класс рекурсивных множеств Ret 67

58 Пусть T = (Q,,,, q 0, F) и T(T) = L. Можно предполагать, что после принятия входной цепочки x L Tm T не делает больше никаких движений, т. е. значение (q, X) не определено для любых q F и X. Класс рекурсивных множеств

59 Класс рекурсивных множеств Построим другую машину Тьюринга T 1 = (Q {p},,, 1, q 0, {p}), у которой одно принимающее состояние p Q. Если (q, X) определено для q Q \ F, X, то 1 (q, X) = (q, X). Если (q, X) не определено для q Q \ F, X, то 1 (q, X) = p.

60 Правила 1 Tm T 1 включают все правила машины T, так что T 1 моделирует T. Кроме того, функция 1 Tm T 1 доопреде- ляется для пар (q, X), q Q \ F, X, для которых движение Tm T не определено, движением, переводящим T 1 в её принима- ющее состояние p. Класс рекурсивных множеств

61 Класс рекурсивных множеств Так Tm T 1 моделирует Tm T до тех пор, пока T не останавливается. Если машина Tm T останавливается в не- конечном состоянии, она, конечно, не принимает свою входную цепочку, но Tm T 1 делает ещё одно движение в состояние p и принимает. Ясно, что Tm T 1 принимает язык \ L. Что и требовалось доказать.

62 Класс рекурсивных множеств Лемма 7.2. Пусть x 1, x 2,... эффективное перечисление всех предложений над некоторым конечным алфавитом, а T 1, T 2,... эффективное перечисление всех машин Тьюринга с символами ленты, выбранными из некоторого конечного алфавита, включающего. Пусть L 2 = { x i x i принимается машиной T i }. Утверждается, что L 2 рекурсивно пере- числимое множество, дополнение которого, т. е. = * \ L 2, не является рекурсивно перечислимым. Ret 66 Ret 67

63 Доказательство. Предложения языка L 2 принимаются машиной Тьюринга T, которая необязательно останавливается на предло- жениях, не принадлежащих языку L 2, и действует следующим образом. 1. Для данного предложения x * машина T перечисляет цепочки x 1, x 2,... до тех пор, пока она не находит цепочку x i = x, тем самым определяя, что x является i-й цепочкой в перечислении. Класс рекурсивных множеств

64 2. Затем T генерирует Tm T i и передает управление универсальной машине Тью- ринга U, которая моделирует Tm T i с входной цепочкой x i. 3. Если T i с входной цепочкой x i останавливается и принимает, то Tm T тоже останавливается, принимая. Если Tm T i останавливается и отвергает x i, то T тоже останавливается, отвергая. Наконец, если Tm T i не останавливается, то Tm T тоже не останавливается. Класс рекурсивных множеств

65 Класс рекурсивных множеств Таким образом, множество L 2 рекурсивно перечислимо, поскольку оно распознаётся Tm T, описанной выше. Теперь не может быть r.e.s., поскольку если бы нашлась машина Тьюринга T j, распознающая, то (1) x j = T(T j ) (2) x j L 2 = T(T j ), то есть x j принимается T j тогда и только тогда, когда x j не принимается T j. Это противоречие означает, что такая Tm T j не существует, т. е. не является r.e.s. Что и требовалось.

66 Класс рекурсивных множеств Пояснение. Поясним утверждение (1) x j = T(T j ) (2) x j L 2 = T(T j ). Утверждение (1) следует из ошибочного предположения о существования Tm T j, распознающей язык. Утверждение (2) следует из определения языка L 2 как состоящего из цепочек, принимаемых Tm T j. языка

67 Класс рекурсивных множеств Теорема 7.2. Существует рекурсивно перечислимое множество, которое не является рекурсивным. Доказательство. Согласно лемме 7.2 L 2 рекурсивно перечислимое множество, дополнение которого не является рекурсивно перечислимым.7.2 Если бы L 2 было рекурсивным, то по лемме 7.1 его дополнение,, тоже было бы рекурсивным и, следовательно, рекурсивно перечислимым, что противоречило бы утверждению леммы Итак, L 2 множество рекурсивно перечислимое, но не рекурсивное. Что и требовалось доказать.

68 § 7.4. Машины Тьюринга и грамматики типа 0 В этом параграфе мы докажем, что язык распознаётся машиной Тьюринга тогда и только тогда, когда он порождается грамматикой типа 0.

69 Чтобы доказать достаточность, мы построим недетерминированную машину Тьюринга, которая недетерминированно выбирает вывод в грамматике и смотрит, совпадает ли результат этого вывода с входной цепочкой. Если да, то машина принимает её. Машины Тьюринга и грамматики типа 0

70 Чтобы доказать необходимость, мы строим грамматику, которая порождает представление любой терминальной строки в виде цепочки нетерминалов грамматики, а затем моделирует действия данной машины Тьюринга на этой строке в терминах вывода. Если входная строка принимается маши- ной Тьюринга, то выведенная строка нетерминалов, моделирующая содержание ленты в терминах вывода, преобразуется в терминальную, которые она представляет. Машины Тьюринга и грамматики типа 0

71 Теорема 7.3. Если язык L порождается грамматикой типа 0, то язык L распознается машиной Тьюринга. Доказательство. Пусть G = (V N, V T, P, S) грамматика типа 0 и L = L(G). Опишем неформально недетерминирован- ную машину Тьюринга T, распознающую язык L. Машины Тьюринга и грамматики типа 0

72 Положим T = (Q, V T,,, q 0, F), где = V N V T {B, #, X}, причём B, #, X V N V T. Мы не задаём всех состояний во множестве Q сразу, но назначаем их, как только в них возникает потребность при построении. Мы разрешаем T печатать пробел B, если необходимо. Машины Тьюринга и грамматики типа 0

73 Сначала T имеет на ленте w V T *. Затем, сдвигая цепочку w на одну ячейку вправо, она вставляет на освободившееся перед w место символ #. Следом за w печатается цепочка # S #. Содержание ленты в этот момент имеет вид # w # S #. С этого момента Tm T будет недетер- минированно моделировать вывод в грам- матике G, начиная с символа S. Каждая сентенциальная форма будет появляться по очереди между двумя последними ограни- чителями # (рабочее пространство). Машины Тьюринга и грамматики типа 0

74 Если некоторый выбор движений приводит к цепочке терминалов на рабочем простран- стве, то она сравнивается с w. Если эти две цепочки равны, то Tm T принимает. Более детально, пусть в какой-то момент Tm T имеет на своей ленте цепочку вида #w#A 1 A 2... A k #. Машина T передвигает свою головку по цепочке A 1 A 2... A k, недетермини- рованно выбирая позицию i и константу r между 1 и максимальной длиной левой части любого правила из множества P. Машины Тьюринга и грамматики типа 0

75 Затем Tm T исследует подцепочку A i A i A i + r – 1. Если она является левой частью (lhs) некоторого правила, то она заменяется правой частью (rhs) этого же правила. Машины Тьюринга и грамматики типа 0

76 При этом, если = | rhs | | lhs |, и 0, то если 0 (правая часть правила короче левой), то Tm T сдвигает последний символ # влево на | |, заполняя ячейки справа от него пробелами B; если 0 (правая часть правила длиннее левой), то Tm T слева от последнего символа # временно вставляет заполнителей X, чтобы дать место для длинной правой части правила. Машины Тьюринга и грамматики типа 0

77 Машины Тьюринга и грамматики типа 0 Из этого простого моделирования выводов в грамматике G должно быть ясно, что Tm T будет печатать на своей ленте строку вида # w # #, где, точно тогда, когда S. Кроме того, если = w, то Tm T принимает. Заметим, что для реализации проверки этого равенства опять пригодится символ X. Что и требовалось доказать.

78 Теорема 7.4. Если язык L распознается машиной Тьюринга, то язык L порождается грамматикой типа 0. Доказательство. Пусть язык L распозна- ется машиной Тьюринга T = (Q,,,, q 0, F). Мы построим грамматику G, которая недетерминированно порождает две копии представления некоторого слова из множе- ства *, а затем моделирует действие Tm T на одной из этих копий. Машины Тьюринга и грамматики типа 0

79 Если Tm T принимает слово, то грамматика G превращает вторую копию в терминальную строку. Если Tm T не принимает слово, вывод никогда не даёт в результате терминальную строку. Снова мы предполагаем без потери общности рассуждений, что для каждого q F и X значение (q, X) не определено. Машины Тьюринга и грамматики типа 0

80 Формально положим G = (V N,, P, A 1 ), где V N = {[X, Y] X { }, Y } Q {A 1, A 2, A 3 }, а P = {(1) A 1 q 0 A 2 ; (2) A 2 [a, a]A 2 для каждого a ; (3) A 2 A 3 ; (4) A 3 [, B]A 3 ; (5) A 3 ; Правила (1)–(5) порождают образ начальной конфигурации Tm T, включая рабочее пространство на её ленте. Машины Тьюринга и грамматики типа 0

81 Правила (6)–(7) воспроизводят движения Tm T вправо и влево соответственно: (6) q[a, C] [a, D] p для каждых a { }, q Q, C, таких, что (q, C) = (p, D, R), где p Q, D ; (7) [b, E] q [a, C] p [b, E] [a, D] для всех C, D, E ; a, b { }, q Q, таких, что (q, C) = (p, D, L), где p Q, D ; Машины Тьюринга и грамматики типа 0 Ret 86

82 Правила (8) восстанавливают входную цепочку Tm T, если она принимается: (8) [a, C] q qaq, q[a, C] qaq, q для каждого a { }, C и q F}. Машины Тьюринга и грамматики типа 0 Ret 90

83 Используя правила 1 и 2, получаем вывод вида A 1 q 0 [a 1, a 1 ] [a 2, a 2 ]... [a k, a k ]A 2, где a i, i = 1, 2,..., k. Предположим, что Tm T принимает цепочку a 1 a 2... a k, используя не более, чем m ячеек справа от своего ввода. Тогда, используя правило 3, затем m раз правило 4 и, наконец, правило 5, продолжим предыдущий вывод. Получаем A 1 q 0 [a 1, a 1 ] [a 2, a 2 ]... [a k, a k ] [, B] m. Машины Тьюринга и грамматики типа 0

84 Заметим, что с этого момента и впредь только правила 6 и 7 могут использоваться до тех пор, пока не порождается принимающее состояние. При этом первые компоненты в обозначениях нетерминалов никогда не изменяются, а вторые моделируют записи, производимые Tm T на её ленте. Машины Тьюринга и грамматики типа 0

85 Машины Тьюринга и грамматики типа 0 I. Индукцией по числу l движений машины T можно показать, что если (q 0, a 1 a 2...a k, 1) (q, X 1 X 2... X s, r), то q 0 [a 1, a 1 ][a 2, a 2 ]... [a k, a k ][, B] m [a 1, X 1 ][a 2, X 2 ]... [a r–1, X r–1 ] q [a r, X r ]... … [a k+m, X k+m ], где a 1, a 2,..., a k ; a k+1 = a k+2 =... = a k+m = ; X 1, X 2,..., X k+m ; X s+1 = X s+2 =... = X k+m = B.

86 База. Пусть l = 0. Утверждение выпол- няется очевидным образом. Индукционная гипотеза. Предположим, что утверждение выполняется для всех l n (n 0). Машины Тьюринга и грамматики типа 0

87 Машины Тьюринга и грамматики типа 0 Индукционный переход. Пусть Tm T выполняет следующие n + 1 движений: (q 0, a 1 a 2...a k, 1) (q 1, X 1 X 2...X r, j 1 ) (q 2, Y 1 Y 2...Y s, j 2 ). Тогда по индукционной гипотезе, применённой к первым n движениям, существует вывод вида q 0 [a 1, a 1 ][a 2, a 2 ]...[a k, a k ][, B] m [a 1, X 1 ][a 2, X 2 ]...q 1 [a j 1, X j 1 ]…[a k+m, X k+m ].

88 Судя по последнему движению, должно быть (q 1, X j 1 ) = ( q 2, Y j 1, D) и D = L, если j 2 = j 1 – 1 или D = R, если j 2 = j Соответственно, при D = R существует правило грамматики вида 6: q 1 [a j 1, X j 1 ] [a j 1, Y j 1 ] q 2 ; при D = L существует правило грамматики вида 7: [a j 1 –1, X j 1 –1 ] q 1 [a j 1, X j 1 ] q 2 [a j 1 –1, X j 1 –1 ][a j 1, Y j 1 ]. Машины Тьюринга и грамматики типа 0

89 Машины Тьюринга и грамматики типа 0 Таким образом, ещё один шаг вывода даёт [a 1, X 1 ][a 2, X 2 ]... q 1 [a j 1, X j 1 ]... [a k+m, X k+m ] [a 1, Y 1 ][a 2, Y 2 ]... q 2 [a j 2, Y j 2 ]... [a k+m, Y k+m ], где X i = Y i для всех i j 1. Итак, вспомогательное утверждение доказано.

90 Машины Тьюринга и грамматики типа 0 Далее, если q F, то по правилам грамматики вида 8 можно получить вывод8 [a 1, X 1 ][a 2, X 2 ]... q [a j, X j ]... [a k+m, X k+m ] q a 1 q a 2 q... q a k q... q a 1 a 2... a k. Итак, доказано, что если a 1 a 2...a k принимается Tm T, то a 1 a 2... a k L(G).

91 Машины Тьюринга и грамматики типа 0 II. Чтобы завершить доказательство теоремы, остается показать, что если A 1 w, то цепочка w принимается Tm T. Прежде всего отметим, что любой вывод и, в частности, вывод A 1 w может начи- наться только по правилам 1–5, дающим результат вида A 1 q 0 [a 1, a 1 ][a 2, a 2 ]...[a k, a k ][, B] m.

92 Машины Тьюринга и грамматики типа 0 Далее могут применяться правила 6 и 7, дающие в конце концов результат вида [a 1, X 1 ][a 2, X 2 ]... q [a j, X j ]... [a k+m, X k+m ], где q F, после чего правила 8 дадут w = a 1 a 2...a k.

93 Машины Тьюринга и грамматики типа 0 Собственно, надо показать, что движения Tm T моделируются на участке вывода q 0 [a 1, a 1 ][a 2, a 2 ]... [a k, a k ][, B] m [a 1, Y 1 ][a 2, Y 2 ]... q [a j, Y j ]... [a k+m, Y k+m ], где q F. Другими словами, если такой вывод имеет место, то существуют движения Tm T вида (q 0, a 1 a 2... a k, 1) (q, Y 1 Y 2...Y k+m, j). Докажем это утверждение индукцией по l длине вывода.

94 База. Пусть l = 0. Утверждение выполняется очевидным образом. Индукционная гипотеза. Предположим, что утверждение выполняется для всех l n (n 0). Машины Тьюринга и грамматики типа 0

95 Машины Тьюринга и грамматики типа 0 Индукционный переход. Пусть имеется вывод длиной l = n + 1. В общем случае имеем q 0 [a 1, a 1 ][a 2, a 2 ]... [a k, a k ][, B] m [a 1, X 1 ][a 2, X 2 ]... q 1 [a j 1, X j 1 ]... [a k+m, X k+m ] [a 1, Y 1 ][a 2, Y 2 ]... q[a j, Y j ]... [a k+m, Y k+m ], где q F. Согласно индукционной гипотезе существует переход (q 0, a 1 a 2...a k, 1) (q 1, X 1 X 2... X k+m, j 1 ).

96 Ясно, что последний шаг вывода мог быть выполнен только посредством правила вида 6 или 7. Если применялось правило вида 6, то j = j 1 + 1; если использовалось правило вида 7, то j = j 1 – 1. Эти правила существуют благодаря тому, что (q 1, X j 1 ) = (q, Y j 1, D), где D = R, если j = j 1 + 1, или D = L, если j = j 1 – 1. Машины Тьюринга и грамматики типа 0

97 При этом X i = Y i для всех i j 1. Благодаря этим значениям функции машина T совершает ещё одно движение, переводящее её в принимающую конфигурацию: (q 0, a 1 a 2...a k, 1) (q 1, X 1 X 2... X k+m, j 1 ) (q, Y 1 Y 2...Y k+m, j), где q F. Другими словами, показано, что w = a 1 a 2...a k принимается Tm T. Итак, если w L(G), то цепочка w принимается машиной T. Теорема доказана полностью. Машины Тьюринга и грамматики типа 0 Next

98 § 7.5. Универсальная грамматика Хомского типа 0 Тройка G = (N, T, P), компоненты N, T, P которой имеют тот же смысл, что и в обычной грамматике Хомского, называется грамматической схемой. Здесь N нетерминалы, T терминалы, P правила грамматики типа 0. Для строки w (N T) * определим язык L(G,w) = {x T * | w * x}, где вывод производится в соответствии с продукциями из P.

Универсальная грамматика типа 0 это грамматическая схема G u = (N u, T u, P u ), где N u, T u непересекающиеся алфавиты, а P u конечное множество переписывающих правил над N u T u, которая обладает таким свойством: для каждой грамматики G = (N, T u, S, P) типа 0 существует такая строка w(G), что L(G u,w(G)) = L(G). 99 Универсальная грамматика Хомского типа 0

Итак, универсальная грамматика модели- рует любую наперёд заданную грамматику G при условии, что код w(G) последней берётся в качестве аксиомы универсальной грамматики. Универсальные грамматики типа 0 в описанном выше смысле существуют. Так как это утверждение лежит в основе последующих рассмотрений, приведём его полное доказательство. 100 Универсальная грамматика Хомского типа 0

101 Сначала мы замечаем, что каждый рекурсивно перечислимый язык может быть порождён грамматикой Хомского, имеющей самое большее три нетерминала. И в самом деле, если язык L порождается грамматикой G = (V N, V T, S, P) и V N содержит больше, чем три элемента, скажем, V N = (S, X 1,..., X m ), где m > 2, то мы определяем гомоморфизм h : V * (V T {S, A, B}) * (где А, В символы, не содержащийся в V) при h(S) = S, h( ) = для всех V T, и h(X i ) = AB i, 1 i m. Положим h(P') = {h(u) h(v) | u v P}. Легко проверить, что L порождается грамматикой G'= ({S, A, B},V T, S, P'). Универсальная грамматика Хомского типа 0

Пояснение. Гомоморфное отображение правил. Любой язык может быть порождён грамматикой Хомского с тремя нетерминалами. Пусть V N = {S, X 1, X 2, X 3 }, V T ={a, b, c, d}, P = {S X 1, S X 1 X 2, X 1 X 2 X 3 X 2, aX 3 X 2 b cd} Введём гомоморфизм для нетерминалов X 1, X 2, X 3 : h(X 1 ) = AB, h(X 2 ) = ABB, h(X 3 ) = ABBB. Тогда правила исходной грамматики отображаются в следующие: P = {S AB, S ABABB, AB ABB ABBB ABB, a ABBB ABBb cd}. Универсальная грамматика Хомского типа 0 102

103 Рассмотрим вывод в грамматике G: S X 1 X 2 aX 3 X 2 b acdb Тот же самый результат можно получить в грамматике G = (N, T, P, S): S AB ABB a ABBB ABB b acdb Очевидно, что L[G ] = L[G]. Код нетерминала исходной грамматики не равного S однозначно восстанавливается по числу букв B, следующих за A. Ясно, что язык, порождаемый грамматикой, не зависит от обозначений нетерминалов. Гомоморфное отображение правил

Построим грамматическую схему G u = (N u, T, P u ), в которой N u = {A, B, C, D, E, F, H, R, Q, S, X, Y} {[a, i] | a T, 1 i 9}, а множество P u состоит из следующих правил: 104 Универсальная грамматика Хомского типа 0

(I) (1) C BQ, (2) Q Q для N T {D, B}, (II)(3) QD [, 2] D [, 1] для N T, (4) [, 2] [, 2] для N T {D, E}, N T, (5) B[,2] [,3] B для N T, (6) [, 3] [, 3] для, N T, (7) [,3] [,4] для N T, (III)(8) [, 1] [, 5] [, 1] [, 1] для, N T, (9) [, 5] [, 5] для N T {D, E}, N T, (10) B[,5] [,6]B для N T, (11) [, 6] [, 6] для, N T, (12) [, 4] [, 6] [, 4] для, N T, 105 Универсальная грамматика Хомского типа 0

(IV) (13) [, 1]E [, 7]E[, 9] [, 8] для, N T, (14) [, 1] [, 7] [, 7] для, N T, (15) D[, 7] D для N T, (16) [, 9] [, 8] [, 9] [, 9] для, N T, (17) [, 8] [, 8] для N T {B, D, E}, N T, (18) [, 9] [, 8] [, 8] [, 9] для, N T, (19) [, 4] [, 8] [, 4] для, N T, (V) (20) [, 1] ED [, 7] RED для N T, (VI) (21) [, 9] D R D для N T, (22) [, 9] R R для N T, (23) R R для N T {D, E}, (24) BR RC, (25) [, 4] R λ для N T, (VII) (26) A A для T, (27) AC H, (28) H H для N T {D, E}, (29) HF λ. 106 Универсальная грамматика Хомского типа 0

Обратим внимание, что нетерминалы вида [α, i], где i {1, 2, 3, 4, 5, 6, 7, 8, 9}, всегда использует α N T, то есть символы грамматики, которая моделируется. Причём символы из T это всегда натуральные терминалы моделируемой грамматики, а символы из N это коды над {A, B}, представляющие нетерминалы модели- руемой грамматики. 107 Универсальная грамматика Хомского типа 0

Допустим, что P = {u i v i | 1 i k}, и рассмотрим code(G)=ASCDu 1 Ev 1 Du 2 Ev 2 D... Du k Ev k DF. Сперва проверим, как грамматическая схема G u действует на строках вида AwCDu i Ev i D... Du k Ev k DF. Группа правил (I) вводит нетерминаль- ный символ Q, который выбирает правило вывода u i v i, расположенное справа от нетерминального символа D (по правилу (3)). 108 Универсальная грамматика Хомского типа 0

По второй группе правил первый символ слова u i преобразуется в [, 1] и нетерминальный символ [, 2], который движется влево, пока не окажется слева от B, где он превращается в [, 3]. Если в w есть вхождение, то по правилу (7) вводится нетерминальный символ [, 4] для того, чтобы закодиро- вать эту информацию. 109 Универсальная грамматика Хомского типа 0

Правила третьей группы заменяют все символы в слове u i на [, 1], а затем каждый такой символ справа от [, 4] стирается, если это возможно сделать с соблюдением порядка. Тем самым, обнаруживается вхождение слова u i в слово w. 110 Универсальная грамматика Хомского типа 0

По правилам группы (IV) каждый символ из v i преобразуется в [, 9] и [, 8]. Последний символ сдвигается влево, пока не окажется слева от B. Когда [, 8] достигнет [, 4], вводится символ. Тем самым, стертая правилами группы (III) строка u i заменяется на v i. Если v i =, то вместо правил группы (IV) используется правило (20). Таким образом, получаем шаг вывода w w', использующий правило u i v i. 111 Универсальная грамматика Хомского типа 0

Эта процедура может повторяться благодаря правилам группы (VI). Если w' содержит вспомогательные символы, то по правилам группы (VII) все их можно стереть, оставив лишь терминальные. Следовательно, L(G) L(G u, code(G)). 112 Универсальная грамматика Хомского типа 0

Для того чтобы доказать обратное включение, заметим, что удалить нетерминальный символ A можно лишь в том случае, когда между A и C стоит терминальная строка. Каждый шаг вывода обязан начинаться с введения символа Q. Стирание этого символа влечёт появление нетерми- нального символа [, 1], который в свою очередь может пропасть лишь при замене его на [, 9]. Эти операции возможны тогда и только тогда, когда подстрока u i удаляется из w. Удаление [, 9] возможно лишь после записи строки v i на месте стертой u i. Появляющийся при этих действиях символ R можно удалить, только когда строка приобретет вид Aw'CDu i Ev i D... Du k Ev k DF. 113 Универсальная грамматика Хомского типа 0

114 Тем самым моделируется шаг вывода, использующий правило u i v i. Все выводы другого вида заблокированы в схеме G u. Таким образом, получено включение L(G u, code(G)) L(G), что завершает доказательство равенства L(G u, code(G)) = L(G). Универсальная грамматика Хомского типа 0

Заметим, что построенная выше универсальная грамматика G u кодирует то, как используется грамматика G в процессе вывода: выбор правила, удаление вхожде- ния его левого члена, запись на это место правого члена правила, проверка того, состоит ли полученная строка лишь из терминальных символов. 115 Универсальная грамматика Хомского типа 0

Пример 7.1. Так как в общем случае code(G) = ASCDu 1 Ev 1 Du 2 Ev 2 D... Du k Ev k DF, то для грамматики G = ({S}, {a}, {S a}, S) имеем code(G) = ASCDSEaDF. 116 Группа правил (I) (1) C BQ, (2) Q Q для N T {D, B} (0) ASCDSEaDF ASBQDSEaDF (1) (1) (1) ASB [S, 2] D [S, 1] EaDF (2) (3) вводит нетерминальный символ Q, который выбирает правило вывода u i v i, расположенное справа от нетерминального символа D (по правилу (3)). Результат применения правил группы (I) показан выше. Итак, начинаем вывод с цепочки ASCSEaDF. По группе (II) правил первый символ ( = S) слова u i преобразуется в [, 1] (в нашем случае [S, 1]), и нетерминальный символ [, 2] (в нашем случае [S, 2]), который движется влево, пока не окажется слева от B. В нашем случае эта ситуация уже достигнута.

117 Затем [, 2] превращается в [, 3] (в нашем случае [S, 3]) с помощью правила (5) B[,2] [,3] B для N T, =ASB [S, 2] D [S, 1] EaDF (2) (2) AS[S, 3] B D [S, 1] EaDF (3) (5) Если в w = S[S, 3] (символы между A и B) есть вхождение = S, то по правилу (7) [,3] [,4] для N T, вводится нетерминальный символ [, 4] для того, чтобы закодировать эту информацию: (3) A[S, 4] B D [S, 1] EaDF (4) (7) Третья группа правил преобразует все символы x из i в (x, 1) (в нашем примере это уже достигнуто); затем каждый такой символ x удаляется справа от (x, 4), в случае, когда такой элемент действительно появляется в том же самом порядке (в нашем примере на этом шагу ничего не происходит). Пример 7.1.

118 (IV) (13) [, 1]E [, 7]E[, 9] [, 8] для, N T, (14) [, 1] [, 7] [, 7] для, N T, (15) D[, 7] D для N T, (16) [, 9] [, 8] [, 9] [, 9] для, N T, (17) [, 8] [, 8] для N T {B, D, E}, N T, (18) [, 9] [, 8] [, 8] [, 9] для, N T, (19) [, 4] [, 8] [, 4] для, N T, = A[S, 4] BD [S, 1]EaDF (4) Из (IV) применимо только (13): (4) A[S, 4]BD[S, 7]E[a, 9][a, 8]DF (5) Из (IV) применимо (15): (5) A[S, 4]BDSE[a, 9] [a, 8]DF (6) (13) (15) Из (IV) применимо (18): (6) A[S, 4]BDSE[a, 8] [a, 9] DF (7) Из (IV) применимо (17): (7) A[S, 4]BDS[a, 8] E [a, 9] DF (8) Из (IV) применимо (17): (8) A[S, 4]BD[a, 8] SE [a, 9] DF (9) Из (IV) применимо (17): (9) A[S, 4]B[a, 8] DSE [a, 9] DF (10) Из (IV) применимо (17): (10) A[S, 4] [a, 8] BDSE [a, 9] DF (11) Из (IV) применимо (19): (11) Aa [S, 4] BDSE [a, 9] DF (12) Пример 7.1.

119 (VI) (21) [, 9] D R D для N T, (22) [, 9] R R для N T, (23) R R для N T {D, E}, (24) BR RC, (25) [, 4] R λ для N T, = Aa [S, 4] BDSE [a, 9] DF (12) Из (VI) применимо (21): (12) Aa [S, 4] BDSERaDF (13) Из (VI) применимо (23): (13) Aa [S, 4] BDSREaDF (14) Из (VI) применимо (23): (14) Aa [S, 4] BDRSEaDF (15) Из (VI) применимо (23): (15) Aa [S, 4] BRDSEaDF (16) Из (VI) применимо (24): (16) Aa [S, 4] RCDSEaDF (17) Из (VI) применимо (25): (17) AaCDSEaDF (18) Пример 7.1.

120 (VII) (26) A A для T, (27) AC H, (28) H H для N T {D, E}, (29) HF λ. = AaCDSEaDF (18) Из (VII) применимо (26): (18) aACDSEaDF (19) Из (VII) применимо (27): (19) aHSEaDF (20) Из (VII) применимо (28): (20) aHEaDF (21) Из (VII) применимо (28): (21) aHaDF (22) Из (VII) применимо (28): (22) aHDF (23) Из (VII) применимо (28): (23) aHF (24) Из (VII) применимо (29): (24) a (25) Пример 7.1.