markov_teorija_algorifmov (522344), страница 65

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 65)

4, здесь фиксируется совокупность исходных слов. Таковыми являются соотношения системы Ь и соотношение 1(2). Допустимыми действиями являются три действия над соотношениями в А, „порождающие" (т. е. позволяющие получать) новые соотношения, исходя из имеющихся. Два из них дают возможность получить соотношения (1) и (2), исходя из имеющегося соотношения 1(!).

Третье применимо к паре имеющихся соотношений 1(1) и (3) с равными левыми частями. Его применение к этим соотношениям дает соогношение (4). Будем говорить о соотношении, что оно выводимо в ассоциативном исчислении Й, если оно может быть получено в результате последовательного применения указанных только что допустимых действий при указанных исходных словах. Будем тогда также говорить, что оно есть следствие из системы Я. Будем говорить о словах Т и и, что они эквивалентны в исчислении й, если соотношение !(!) выводимо в Й. Для выражения эквивалентности слов Р и 9 в исчислении й будем применять прежнюю запись 6 (1). Мы имеем, таким образом, два различных определения ассоциативного исчисления в алфавите А, определяемого системой соотношений !В.

Каждому из них соответствует свое пронлвмд тождествл для пол»трупп ггл. уи~ 4 Б7! дссоцидтнвныв исчисления 349 понятие эквивалентности слов. Эти два понятия эквивалентности оказываются, однако, равносильными, что выражается следующей теоремой. 7.1. Пусть ~ — система соотношений в алфавите А; Й— ассоциативное исчисление, определяемое системой Я в смыв«г п. 4; 6 — ассоциативное исчисление, определяемое систвмой Ь в только чтоукаэанном смысле. Для того чтобы слова Р и Я были эквивалентны в к), необходимо и достаточно, чтобы они были эквивалентны в Й.

Доказательство мы предоставляем читателю. Поскольку понятие эквивалентности слов можно считать основным в теории ассоциативных исчислений, два сформулированных выше определения ассоциативного исчисления оказываются в известном смысле равносильными. В дальненшем мы, говоря об «ассоциативном исчислении, определяемом системой соотношений з в алфавите А», будем (при отсутствии соответствующих оговорок) понимать этот термин в смысле п.

4. 8, Теорию ассоциативных исчислений можно рассматривать как некоторый конструктивный подход к так называемым ассоциативным системам, которые в литературе часто называют полугруппами, Действительно, пусть Й вЂ” ассоциативное исчисление в алфавите А. В силу 6.2 — 6.4, мы имеем тогда возможность применить к словам в А абстракцию отождествления, отождествляя слова, эквивалентные в Й, т.

е. рассматривая слова в А с точностью до эквивалентности в Й. 'Гак рассматриваемые классы слов в А будут играть роль элементов подлежащей построению ассоциативной системы. Будем для краткости называть их просто элементами. Мы можем далее определить умножение элементов как дайн ствие, соответствующее построению соединения представляющих эти элементы слов. Однозначность так определенноГО умножения обеспечивается свойством эквивалентности 6 6' сочетательный закон умножения — сочетательным законом соединения слов.

Мы получаем, таким образом, некоторую ассоциативную систему. Будем говорить, что она порождается ассоциативным исчислением Й. Ассоциативные системы, порождаемые ассоциативными исчислениями, будем называть К-систгмами '). «: ) Буква К здесь происходит от термина «конечно опрсдсленнав система». Нетрудно видеть, что всякая К-система имеет единицу.

В самом деле, роль единицы К-системы играет элемент ее, представляемый пустым словом. Нетрудно далее видеть, что всякая К-система имеет конечное множество производящих элементов. Пусть, в самом деле, К-система С порождается ассоциативным исчислением Й в алфавите А. Как легко видеть, элементы системы С, представляемые буквами алфавита А, образуют систему производящих элементов системы С: всякий отличный от единичного элемент системы С может быть представлен в виде некоторого произведения (с возможными повторениями множителей) этих элементов. Элементы К-системы С, представляемые словами Т и У, тогда и только тогда тождественны, когда зти слова эквивалентны в Й.

Понимая в данном случае термин «ассоциативное исчисление» в смысле п. 7, мы можем сказать, что зти слова тогда и только тогда тождественны, когда соотношение 1(1) выводимо в нашем исчислении, т. е. когда оно является следствием из З. Это положение дел можно коротко выразить, сказав, что система Я есть полная система соотношений между производящими элементами ассоциативной системы С. 9. Ввиду того, что элементы К-системы представляются . ловами в алфавите порождающего ее ассоциативного исчисления, естественно возникает вопрос о распознавании тождества элементов, представленных двумя разными словами. Тождественными этн элементы являются тогда и только тогда, когда представляющие их слова эквивалентны в порождающем ассоциативном исчислении.

Таким образом, распознавание тождества элементов К-систем сводится к распознаванию эквивалентности слов в ассоциативных исчислениях. Для всяких слов Р и «г в алфавите ассоциативного исчисления Й может быть поставлена единичная проблема распознавания эквивалентности этих слов в Й: верно ли, что Й: РЯЦ? Всякому данному ассоциативному исчислению Й соответствует класс единичных проблем этого рода. Массовая алгорифмическая проблема, соответствующая этому классу, состоит в разыскании единого общего конструктивного метода, позволяющего узнавать для любых двух данных слов Р и (1, являются ли они эквивалентными в Й.

Эту проблему мы будем называть проблемой эквивалентности для ис. числения Й. збо пРОБлемА тождестВА для пОлкгРупп !Гл, чн! Ввиду того, что эквивалентность двух слов в ассоциативном исчислении й, порождающем К-систему С, равносильна тождеству представляемых ими элементов системы С, проблему эквивалентности для й можно также рассматривать как проблему тождества для С, т.

е. как проблему построения единого общего конструктивного метода, позволяющего узнавать для любых двух элементов системы С, заданных представляющими их словами, тождественны ли эти элементы. Этим определяется роль проблемы эквивалентности для ассоциативного исчисления Й в исследовании порождаемой этим исчислением ассоциативной системы. Как всякая массовая проблема, проблема эквивалентности для ассоциативного исчисления й допускает уточнение в терминах теории алгорифмов — она может быть поставлена как нормальная массовая проблема 5 46!. Для этого нам необходимо лишь условиться в определенном способе записи единичных проблем эквивалентности слов в алфавите исчисления Й. Всякаятакаяединичнаяпроблема определяется парой слов в алфавите исчисления. Для этого может быть использован любой знак, не являющийся буквой этого алфавита.

Мы будем предполагать, что звездочка зв является таким знаком, и будем записывать пару слов Р и 11 в виде (1) Ргали. Проблема эквивалентности для ассоциативного исчисления й в алфавите А ставится тогда как нормальная массовая проблема следующим образом. Ищется нормальный алгорифм над алфавитом Аз1г, применимый ко всякому слову вида (1), где Р и Я вЂ” слова в А, и перерабатывающий слово (1) в пустое слово тогда и только тогда, когда й: Рак!. Эту проблему мы и будем в дальнейшем называть проблемой вквивалентности для ассоциативного исчисления й. В следующем параграфе мы укажем построение ассоциативного исчисления, для которого проблема эквивалентности неразрешима.

$58. Построение ассоциативного исчисления с неразрешимой проблемой эквивамнтности 1. Для построения ассоциативного исчисления с неразрешимой проблемой эквивалентности мы свяжем ассоциативные исчисления с нормальными алгорифмами посредством следующей теоремы (А. А. М а р к о в 121, 71, 5 2.1.1): йбв1 неРАзРешимОе АссОциАтиВнОе исчисление 35! 1.1. Пусть и, р, о — отличные друг от друга буквы, не принадлежаи(ие алфавиту А. Тогда, каков бы ни был нормальный алгорифм й в алфавите А, может быть построено такое ассоциативное исчисление В над огфовитом Аиро, что равенство й(Р) ХЯ будет иметь место для слов Р и Я в А тогда и только тогда, когда (1) 9; пррп'й ИЯИ.

В самом деле, пусть алгорифм Й имеет схему (2) (П! У, (1 =1<У), где П,— слова в А, а каждое У! либо тоже есть слово в А, либо получается из слова в А посредством присоединения точки слева'). Пусть (1 <1< 1ч'; $ — буква А; Х вЂ” слово в А; !$Хг = 1;; $Х ф П!) (1<а< У; Х вЂ” слово в А; Ха <1.) (1<1< л1; У! — слово в А) (1 <! < 1т'; У;я.

У;) (1<!< )У) (1 < ! < Аг+ 1; й — буква А). р сХ ~-+ 1ргХ р,Хпе-ьо, зХп ргП! ео о,У! р;П!+-ь ок.„гУ; лог е-ь и рг $о, е-ь ог', ") Мы позволим себе такой не слишком точный способ говорить о Заключительных формулах полстановок алгорифма И. Б == Аиро. Введем буквы р, (2 < ! < А1), и! (1 < ! < А!), отличные друг от друга и от букв алфавита Б; положим Р! Р она ! о. Обозначим через Р и С алфавиты, состоящие из букв р! (1<!< 1У) и о! (1< !'< А!+1) соответственно.

Положим затем В чы АРСп и построим ассоциативное исчисление зВ в алфавите В, определяемое следующей сокращенно записанной системой соотношений: пРОБлемА тОждествА для пОлуГРупп 352 !гл. югг ! Здесь Х в соотношениях первых двух групп — произвольное сл ово условиям. Так как эти ф, удовлетворяющее записанным справа в скоб ках у .

ак эти условия ограничивают сверху длину Х, первые две группы соотношений содержат конечное число соот- ношений, причем все эти соотношения могут быть явно выпиния третьей группы соответствуют простым формулам подстановок алгорифма Й; соотношения четв г ппы — за ни четвертой и4-яг ппыс ру — аключительным формулам подстановок. В 3- сего -я После ние ру оотношений содержат вместе У соотноше ний. ниах. д две группы соотношений не нуждаются д ся в пояснелйы покажем, что так построенное ассоциативное исчисле- ние удовлетворяет условию, сформулированному в теореме .. Для этого вве дем некоторые вспомогательные термины и докажем некоторые леммы.

(1 <Е(У, о 1<»' Будем называть оперативными буквами б уквы рг ) ог ( <1<У+1). Будем называть специаль- ными словами слова вида яг;Сц)ггп, где 9 и гг — сл гово я, спе иал 㫠— слова в А, «1 — оперативная буква. И г р, ц льными словами мы будем называть ело — ва. начг алфавите В, начи т слова в и, не со е жа и ф, нающиеся буквой и, оканчивающиеся бу д р щ е других вхождений ч и содержащие ровно уквой одно вхождение оперативной буквы. Следующие свойства любого из соотношений системы (3) усматриваются непосредственно: 1.2.

Характеристики

Список файлов книги