Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
§ I.4J
МАШИНЫ ТЬЮРИНГА
47
Ясно, что машина Mi имитирует все х-вычисления машины М, и если среди них имеется хоть одно полное, то она рано или поздно это обнаружит, а в противном случае будет работать вечно. Возможность обеспечить детерминированность Mt очевидна.
Пусть М — ДЭ-машина с входным алфавитом V и рабочим алфавитом W, причем V ? W, и / — функция, определенная на некотором подмножестве множества V* и принимающая значения также из V*. Мы скажем, что машина М вычисляет функцию /, если [х, ^-вычисление машины М для любых х, у е V* существует тогда и только тогда, когда у == f(x).
Теорема 1.3. а) Для всякой ДЭ-машины, вычисляющей некоторую функцию, можно построить ДЭ-ма-шину, допускающую множество значений этой функции. б) Для всякой ДЭ-машины М можно построить ДЭ-ма-шину, вычисляющую функцию с множеством значений L{M).
Доказательство, а) Пусть ДЭ-машина М с входным алфавитом V и рабочим алфавитом W вычисляет функцию /. Построим Э-машину Afi, работающую так: сначала на рабочей ленте записывается произвольная цепочка геУ* и к ней приписывается справа символ йф У U W; потом Му работает как п. о. м. машины М, после чего на рабочей ленте оказывается записанной цепочка zdf(z) (если только f(z) определена; в противном случае Mi работает вечно); затем входная цепочка х (которая до этого не читалась) сравнивается с цепочкой f(z); если окажется х — f(z), и только в этом случае, рабочая лента уничтожается, и машина переходит в заключительное состояние. Ясно, что допускает как раз множество значений f. Остается воспользоваться теоремой 1.2.
б) ДЭ-машина Mi, которая сначала переписывает входную цепочку на рабочую ленту, затем работает как п. о. м. данной машины М и, наконец, в случае успешного окончания работы уничтожает «разграничитель» d, будет вычислять функцию, принимающую значение х для любого x^L(M) и не определенную вне L(M).
Выясним теперь взаимоотношение между Э-машина-ми и грамматиками.
48
ОСНОВНЫЕ понятия
[ГЛ. I
Будем говорить, что грамматика Г и Э-машина М эквивалентны, если L(T) =L(M). Аналогично определяется эквивалентность двух Э-м а ш и н.
Теорема 1.4. а) Для всякой Э-машины можно построить эквивалентную ей грамматику, б) Для всякой грамматики можно построить эквивалентную ей Э-машину.
Доказательство, а) Пусть М — данная Э-машина с входным алфавитом V и Мi — ее п. о. м. По легко построить машину М2, имеющую такие два состояния q' и q", что при х е V* из ситуации^', А, фф, А, ф х) тогда и только тогда достижима ситуация (q", А, ф Ф, А, ф), когда xei (М). Построим теперь грамматику Г следующим образом. 1) Основной словарь Г есть V. 2) Вспомогательный словарь Г есть (W—У) IJ Q U {/}, где W и Q — соответственно рабочий алфавит и множество состояний машины М2 и
I ф. V U W U Q. 3) Начальный символ Г есть /. 4) Схема Г состоит из правил I-* ф q, фд'^А и правил, определенным образом сопоставляемых инструкциям машины М2, а именно: каждой инструкции 8qa-*q^ типа (ii) сопоставляется правило qf,-*bqa\ каждой инструкции типа (iii) —правило 8q^-^qa; каждой
инструкции qa~*qв Л типа (iv) — всевозможные правила вида q$y -*? VQa, где yef, и каждой инструкции вида qa-+q& П типа (v)—всевозможные правила вида yq$ -> qay, где y^W. Таким образом, схема грамматики Г представляет собой «обращение» программы М2; поэтому, какова бы ни была цепочка х е V*, в грамматике Г тогда и только тогда можно вывести ф q'x из Ф q", или, что то же самое, х из /, когда в М2 ситуация (Я", А, ф ф, А, ф) достижима из (q', А, ф ф, А, ф х). Отсюда L(T) —L(M).
б) Пусть Г = (V, W, /, R} — произвольная грамматика.
Построим Э-машину М с входным алфавитом V и рабочим алфавитом V [) W, которая будет сначала переписывать входную цепочку на рабочую ленту, затем производить на рабочей ленте произвольный вывод в Г в о'братном порядке, а потом в случае, когда в результате такого «обратного вывода» на рабочей ленте останется только символ I, уничтожать его и переходить
МАШИНЫ ТЬЮРИНГА
49
в заключительное состояние; при этом можно сделать так, чтобы ни в каком другом случае заключительное состояние не наступало. Очевидно, L(M) =L(T).
Подведем итог. В силу только что доказанной теоремы класс языков, порождаемых грамматиками, совпадает с классом языков, допускаемых Э-машинами. Этот последний ввиду теорем 1.2 и 1.3 совпадает с классом множеств значений функций, вычисляемых ДЭ-машина-ми. Но легко видеть, что ДЭ-машинами вычисляются в точности те же функции, что и обычными одноленточными машинами Тьюринга (упражнение 1.20), т. е. частично рекурсивные функции *); множества же значений частично рекурсивных функций суть рекурсивно перечислимые множества. Итак, из теорем 1.2—1.4 вытекает
Теорема 1.5. Класс языков, порождаемых грамматиками, совпадает с классом рекурсивно перечислимых языков.
Теперь мы можем разъяснить сделанное в § 1.2 утверждение, что «порождающий» способ описания языков не уступает по силе никакому другому эффективному способу. Именно, в силу доказанных теорем это утверждение немедленно вытекает из тезиса Черча, согласно которому всякая функция, допускающая вычисление каким-либо эффективным в интуитивном смысле способом, частично рекурсивна. Вместе с тезисом Черча наше утверждение носит, разумеется, не математический, а естественнонаучный характер.
