Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Итак, доказана
Теорема. Множество теорем туэвской системы (T) совпадает с множеством теорем полутуэвской системы (ST)2.
Иначе говоря, продукции, добавляемые к (ST)2, чтобы получить (T), ведут не к новым теоремам, а только к некоторым вариантам доказательств.
6.1.4. Резюме полученных результатов
На протяжении нескольких последних глав мы доказали ряд теорем об эквивалентности различных концепций алгоритма. Добавим к ним еще следующий результат (его доказательство104
Часть /. Предварительные сведения из логики и алгебры
предоставляется читателю в качестве упражнения): всякой туэь-ской системе можно поставить в соответствие систему Поста с тем же множеством теорем.
Общую картину можно представить следующий схемой:
Всякое множество, порождаемое одной из указанных на схеме систем, может быть порождено и любой другой из них; для любой данной системы может быть эффективно построена эквивалентная ей система другого типа.
Из эквивалентности машин Тьюринга и формальных систем следует
Теорема. Всякое рекурсивно перечислимое множество может быть порождено любой из следующих систем: полутуэвской системой, туэвской системой, нормальной системой, системой Поста.Г л. VI. Комбинаторные системы и машины Тьюринга
105
6.1.5. Упражнения
1. Доказать, что (ST) і — моногенная система.
2. Доказать, что в туэвской системе для всякой теорейы существует доказательство без повторений.
§ 6.2. НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ
6.2.1. Следствия из неразрешимости проблемы остановки
Выше мы рассматривали следующую проблему: существует ли общий алгоритм (машина Тьюринга), который всегда отвечал бы однозначно («да» или «нет») на любой вопрос следующего типа: «Если данная машина Z начнет вычисления с данного числа пг, то получит ли она результат?»
В общем виде эта проблема решается отрицательно. (Внимание: в некоторых частных случаях тот же самый вопрос может получить положительный ответ!)
Построение систем (ST)2 и (T), соответствующих машине Z в смысле § 6.2, позволяет сопоставить аргументам машины Z теоремы систем (ST)2 и (T). Выбрав в качестве Z такую машину, для которой проблема остановки неразрешима, мы увидим, что в соответствующих туэвской и полутуэвской системах рекурсивно неразрешима проблема доказуемости. (Эта проблема состоит в следующем: можно ли указать алгоритм, позволяющий для любого слова в алфавите системы отвечать «да» или «нет» на вопрос о том, является ли это слово теоремой системы?)
Строя нормальную систему и систему Поста, соответствующие полутуэвской и туэвской системам (см. § 3.2), мы также получим системы, в каждой из которых проблема доказуемости неразрешима.
6.2.2. Проблема тождества
Вернемся теперь к проблеме тождества, или эквивалентности слов, сформулированной в первой главе. Пусть некоторая фактор-полугруппа свободной полугруппы задается с помощью п соотношений Туэ: Pi ~ Q1, ..., Pn — Qn; спрашивается, может ли быть установлено алгоритмически, эквивалентны ли в этой факторпо-лугруппе два заданных слова А и В?
Рассмотрим туэвскую систему с аксиомой А и продукциями P1 ++ Q1, ..., Pn Qn.
Установить, эквивалентно ли слово А слову В, или выяснить, является ли В теоремой данной туэвской системы, — это равносильные проблемы.
Возьмем теперь построенную нами туэвскую систему с неразрешимой проблемой доказуемости и сопоставим ей полугруппу, полученную путем замены каждой пары туэвских продукций соответствующим соотношением Туэ; ясно, что для этой полугруппы проблема тождества неразрешима,106
Часть /. Предварительные сведения из логики и алгебры
6.2.3. Проблема соответствий Поста
Пусть имеются следующие русские слова1): M1 = «ГА» (сокращение от гектар), N1 = «А» (союз),
M2 = «ПИР» (праздник с обильной едой), N2 = «ПИ» (буква я), M3 = «О» (предлог), N3 = «РОГ» (у коровы). Рассмотрим слово
«ПИРОГА» (полинезийская лодка). Это слово может быть разбито на части двумя способами
ПИР/О/ГА
и
ПИ/РОГ/А;
тем самым из M можно сделать две шарады:
M = M2M3M1 = N2N3N1,
исходя из троек (Mu M2, M3) и (Nu N2, N3) и соблюдая следующее условие: если слово Mi выступает в одной шараде на /-м месте, то соответствующее слово N{ выступает в другой шараде также на /-м месте.
Проблема двойной шарады. Пусть имеются две п-ки слов в алфавите
(G1..... Gn) и (Hi.....Hn))
спрашивается, существует ли конечная последовательность индексов i1, i2, ..., ih, такая, что можно построить двойную шараду
GhGi2 ... Gik = HiiHi2... Hlk (ї/є={ 1,2.....п}).
На этот частный вопрос иногда можно ответить положительно (построив, быть может, соответствующий пример), а иногда — отрицательно (указав какую-либо принципиальную невозможность например, построить двойную шараду невозможно, если всякое Gi длиннее, чем соответствующее Ні).
Проблема Поста. Здесь, однако, встает и другая, общая проблема, сформулированная Постом: «Существует ли общий алгоритм, который для всяких двух п-ок слов в данном алфавите решал бы, существует ли последовательность индексов, обеспечивающая указанное соответствие?»