Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 37

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 31 32 33 34 35 36 < 37 > 38 39 40 41 42 43 .. 101 >> Следующая


Итак, доказана

Теорема. Множество теорем туэвской системы (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 длиннее, чем соответствующее Ні).

Проблема Поста. Здесь, однако, встает и другая, общая проблема, сформулированная Постом: «Существует ли общий алгоритм, который для всяких двух п-ок слов в данном алфавите решал бы, существует ли последовательность индексов, обеспечивающая указанное соответствие?»
Предыдущая << 1 .. 31 32 33 34 35 36 < 37 > 38 39 40 41 42 43 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed