Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
(st),
1) Доказательство «слева направо». Включение
означает, что существует вычисление, начинающееся с m при состоянии qi. Иначе говоря, существует конечная последовательность конфигураций
«1, O2, • • •» ап>
где «і = hqimh, ап—заключительная конфигурация и аі->аг+і, [ Ki < п.
Таким образом, мы имеем Ь а„, и ситуация, фигурирующая
(st)1
в ап, не встречается в левых частях команд машины Z. Но к ап можно применить продукцию типа (г) PqiSjQ -> PqSjQ, а затем — продукции типов (д), (е) и (ж), так что в конце концов получится hrh.
2) Доказательство «справа налево». Из рассмотрения продукций типов (г), (д), (е) и (ж) вытекает, что любое доказательство, ведущее к hrh, обязательно проходит через теорему вида hPoqQoh и что в (ST)i для hP0qQ0h существует доказательство Mi, M2, ..., Mn.
Таким образом, мы имеем Mi = hqmh, Mn = hP0qQ0h и Mi —* ->Mi+1, 1 Ki < п.
Существует целое число s, такое, что s < п и что всякое Mu \Ki Ks, содержит некоторое qae причем Ms есть заключительная конфигурация машины Z. Следовательно, m е Pz.
Замечания о строении системы (ST)i. Следует обратить внимание на то, что в (ST)i от числа m зависит только аксиома hqiinh; алфавит и продукции системы от m не зависят. В качестве упражнения можно доказать, что система (ST)i моно-генна (см. ниже п. 6.1.5, упр. 1).
Если m принимает значения из множества неотрицательных Целых чисел, то мы получим семейство полутуэвских систем типа (ST)1. С помощью этого семейства множеству тех чисел т, к которым применима Z1 ставится в соответствие единственная теорема hrh. 102
Часть /. Предварительные сведения из логики и алгебры
Эта ситуация подсказывает мысль об обращении указанного подхода с тем, чтобы построить систему, которая, исходя из аксиомы hrh, выдавала бы в качестве заключительных теорем все целые числа, к которым применима Z.
6.1.2. Машины Тьюринга и полутуэвские системы
Рассмотрим систему (ST)2, полученную из семейства систем типа (Sr)i следующим образом: . аксиомой системы (ST)2 является выражение hrh; .. продукциями системы (ST)2 являются обращения продукций систем (Esr)I (напомним, что все эти системы имеют одно и то же множество продукций).
Проведенное выше исследование систем типа (ST)1 показывает, что следующие утверждения равносильны: «hqifnh является начальной конфигурацией машины Z, приводящей к некоторому результату» и «hqifnh является теоремой системы (ST)2».
Теорема. Машина Тьюринга Z применима к m в том и только в том случае, если выражение hqifnh является теоремой полутуэвской системы (ST)2, которая получается «обращением» систем (ST)u сопоставляемых парам (Z,m).
Замечание. Можно дополнить (ST)2 продукциями, позволяющими стирать h и qu Построенная таким образом система (ST)s позволяет записать наш результат более элегантно:
h m.
(st),
6.1.3. Машины Тьюринга и туэвские системы
В предыдущем пункте машине Тьюринга Z ставилась в соответствие полутуэвская система; теперь мы поставим ей в соответствие туэвскую систему.
Рассмотрим систему (7") с тем же алфавитом, что и раньше, имеющую . аксиому hrh;
.. множество продукций, представляющее собой объединение множеств продукций систем (ST)1 и (ST)2.
Система (T) является туэвской, поскольку продукции системы (ST)2 суть обращения продукций систем (574) і.
Покажем, что множество теорем системы (7") совпадает с множеством теорем системы (ST)2.
В силу нашего построения очевидно, что всякая теорема системы (ST)2 есть теорема системы (T): в самом деле, (T) имеет ту же аксиому, что и (ST)2, и располагает всеми продукциями системы (ST)2.
Перейдем к обратному утверждению. Г л. VI. Комбинаторные системы и машины Тьюринга
103
Обозначим через Ri, R2.....Rt продукции системы (ST)2 и
через Si, S2.....St — их обращения, т. е. продукции системы
(ST)1.
Нетрудно заметить, что введение S,- позволяет «удлинять» доказательство; например, «кусок» доказательства
M (в силу Ri) -*N (в силу R2) -+P можно «удлинить» следующим образом:
M (в силу Ri) -*N (в силу S1) —и т. Д.
По существу нам нужно доказать, что (T) не содержит никаких теорем, помимо теорем системы (ST)2, хотя и может содержать более длинные доказательства.
Итак, пусть имеется доказательство слова M в (T). Выкинем все «бесполезные» шаги, полученные повторениями, и доказательство примет вид
hrh = Mi, M2, ..., Mp = М.
Возможно, что в этом доказательстве выступают только продукции системы (ST)2; в таком случае теорема доказана.
Допустим поэтому, что при переходе от Mj к Mf+l (1 Kj<p) появляется в первый раз продукция типа S, т. е. продукция, отсутствующая в (ST)2.
Может ли M быть аксиомой hrh? Мы видели, что в (ST)1 выражение hrh является заключительной теоремой, так что ни одна обратная продукция, т. е. продукция из (ST)2, не может привести к hrh. Поэтому Mi должно быть следствием из Mj-1 в силу некоторой продукции Ri; другими словами, Mj-1 выводится из Mj с помощью применения правила типа S.
Однако тогда получается, что из Mj с помощью продукций типа S можно получить следствия М;+1 и Mj-i, которые должны быть различными в силу того факта, что из доказательства слова M были устранены все повторения. Этот результат противоречит моногенности системы (ST) і.
