markov_teorija_algorifmov (522344), страница 72
Текст из файла (страница 72)
Если б — гомоморфизм й в В, а лл — гомоморфизм В в 6, то нормальная композиция (!гльб) есть гомоморфизм 6 в 6. 2. Пусть Й и 9 — ассоциативные исчисления в алфавитах А и Б соответственно, а К вЂ” гомоморфизм й в В. Будем говорить, что б есть изоморфизм Й в В, если выполняется условие Г.4.
Если Р и ('1 †сло в А такие, что В: б (Р) 1 б (ге), то й: Р)) Я. Легко проверить, что имеет место утверждение 2.1. Если К вЂ” иэоморфизм Я в В, а Ь вЂ” изоморфизм В в 6, то (лльб) есть изоморфизм Я в 6. 3. Пусть Я и  — ассоциативные исчисления соответственно в алфавитах А н Б, а б — гомоморфизм Я в В. Будем говорить, что б есть гомоморфизм Й на В, если выполняется условие Г.5.
Имеется нормальный алгорифм Е над А Б Б, перерабатывающий всякое слово в алфавите Б в некоторое слово в алфавите А и такой, что для любого ге в Б имеет место эквивалентность В: 6(6(ге)) )) гч. 3.1. Если б — гомоморфизм й на В, а Ь вЂ” гомоморфизм В на 6, то (лльб) есть гомоморфизм Й на 6. Нетрудно показать, что 3.2. Если б — гомоморфизм й на 9, то В: 6(л))) л. 4.
Под иэоморфизмом й на В мы понимаем гомоморфизм Й на В, являющийся вместе с тем изоморфизмом Й в В. Из 2.1 и 3.1 вытекает следующее утверждение: 4.1. Если К вЂ” изоморфизм й на В, а Ъ вЂ” иэоморфизм 9 на 6, то (лльб) есть изоморфизм Й на 6. Очевидно, что 4.2. Тождественный нормальный алгорифм в алфавите ассоциативного исчисления й есть изоморфизм Й на самого себя.
Нетрудно проверить следующее утверждение: 4.3. (Луспгь Я и  — ассоциативные исчисления в алфавипигх А и Б соответственно, б — изоморфизм й на В, а Š— нормальный алгорифм над А 0 Б, перерабатывающий всякое слово в алфавите Б в некоторое слово в алфавите А и удовлетворяющий условию 3(1), Тогда Ф есть изоморфиэм В на Й.
5. Пусть Й и  — ассоциативные исчисления. Будем говорить, что Й включаемо в В, если имеется изоморфизм Й в В. Будем говорить, что й изоморфно В, если имеется изоморфизм Й на В. Из 2.1 следует 5.1. Если исчисление й включаемо в 9, а В вк,гючаемо в 6, то й включаемо в 6. Принимая во внимание, что всякий изоморфизм Я на В является нзоморфизмом Й в В, получаем 5.2.
Если исчисление 21 изоморфно В, то й включаемо в В. Из 4.2 следует, что 5.3. Всякое ассоциативное исчисление изоморфно салгому себе. Из 4.1 следует, что 5.4. Если исчисление Й изоморфно В, а В изоморфно 6, то Й изоморфно 6. С помощью 4.3 нетрудно проверить, что 5.5. Если исчисление Я изоморфно 9, то В изоморфно й. Для дальнейшего будет полезно следующее простое утверждение: 5.6. Луспгь А — произвольный агфавит, а п — положительное натуральное число. Тогда всякое ассоциативное исчисление в алфавипм из и букв изоморфно некоторому исчислению в алфавигпе, не имеющем с А общих букв и также состоящем из и букв. Как легко понять, после выбора соответствующего алфавита определяющая система соотношений искомого исчисления в данном случае может быть получена пз системы соотношений исходного исчисления простым переименованием фигурирующих в ней букв. 6.
Пусть Р— какое-нибудь свойство ассоциативных исчислений. Мы будем говорить, что Р инвариантно, если всякое ассоциативное исчисление, нзоморфное исчислению со свойством Р, само обладает им. Будем говорить, что Р нас,гедственно, если всякое ассоциативное исчисление, включаемое в исчисление со свойством Р, само обладает нм. Очевидным образом имеем 6.1.
Всякое наследственное свойство ассоциативных исчис. лений инвариантно. Приведем некоторые примеры наследственных свойств. 392 ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП )ГЛ. У)!1 Об ассоциативном исчислении Й будем говорить, что оно единично, если всякие два слова в его алфавите эквивалентны в Й (или если — что то же самое — всякое слово в его алфавите эквивалентно в Й пустому слову).
Без труда доказывается, что 6.2. Единичность — наследственное свойство ассоциативных исчислений. 6.3. Единичное ассоциативное исчисление включаемо во всякое другое ассоциативное исчисление. 6.4. Всякое единичное ассоциативное исчисление изоморфно любому другому единичному ассоциативному исчислению. 6.5. Если Й вЂ” единичное ассоциативное исчисление, то для единичности ассоциативного исчисления»В необходимо и достаточно, чтобы »с! было изоморфно й. Об ассоциативном исчислении Й будем говорить, что оно конечно, если имеется такая непустая система слов в алфавите этого исчисления, что всякое слово в его алфавите эквивалентно в Й одному нз членов этой системы.
Без особого труда может быть показано, что 6.6. Конечность ассоциативных исчислений есть наследственное их свойство. Об ассоциативном исчислении Й в алфавите А мы будем говорить что оно полугрупповое*), если для любых Р, и В в алфавите А выполняются следующие условия: 1. если Й: РВ ~~ )~)7, то й: Р )! );); 2. если Й: !ТР !' В)г, то Й: Р й )е. Без особого труда устанавливается, что 6.7. Полугрупповость ассоциативных исчислений есть наследственное их свойство. Об ассоциативном исчислении Й в алфавите А мы говорили (см. С.370), что оно групповое, если имеется нормальный алгорифм (у над А, перерабатывающий всякое слово в алфавите А в слово в этом же алфавите и такой, что для всякого Р в А имеют место эквивалентности Й: Р$(Р) (( Л и й: 3(Р) Рй Л.
Групповость ассоциативных исчислений не является их наследственным свойством. Действительно, исчисление в ал- е) Полугрупповые ассоциативные исчисления в литературе часто называют «конечно определенными повугруппами с сокращением». 66)) ПРОБЛЕМЫ РАСПОЗНАВАНИЯ СВОЙСТВ ИСЧИСЛЕНИЙ 393 фавите аЬ, определяемое системой соотношений ( аЬч-» Ьа +-», является, как нетрудно видеть, групповым, а включаемое в него ассоциативное исчисление в алфавите а, определяемое пустой системой соотношений, не является групповым. Нетрудно показать, что 6.8. Групповость ассоциативных исчислений есть их инвариантное свойсгпво.
6.9. Всякое групповое ассоциативное исчисление является полугрупповым. Из 6.9, и 6.7 следует, что 6.10. Всякое ассоциативное исчисление, включаемое в групповое, является полугрупповым. С помощью 5.1 легко получается, что 6.11. Включаемость ассоциативного исчисления в групповое есть наследственное свойство. Пусть»)с не является !буквой алфавита А. Ассоциативное исчисление Й в алфавите А мы будем называть разрешимым, если имеется нормальный алгорифм над А»К, распознающий среди прочих слов в этом алфавите слова вида Р»)с)'), где Р и )~ — слова в А, для которых имеет место эквивалентность Нетрудно показать, что 6.12.
Разрешимость ассоциативных исчислений есть наследственное их свойство. Ассоциативное исчисление Й мы будем называть абелевым, если для любых слов Р и 9 в его алфавите имеет место эквивалентность Й: РО. Я ОР. Легко усматривается, что 6.13. Абелевосп)ь ассоциативных исчислений есть наследсгг)- венное их свойство. 7. С точки зрения алгебры инвариантные свойства ассоциативных исчислений представляют интерес в первую очередь. Алгебраист будет склонен отождествлять изоморфные ассоциативные исчисления, считая их лишь различными способами задания одной и той же „абстрактной ассоциативной сис)ечы". Прн такой установке неннпарнантные свойства ассоциативных исчислений не представляют особого интереса, пэоьлемА тождествА для полэгьэпп [гл.
Рш $40 ПРОБЛЕМЫ РАСПОЗНАВАНИЯ СВОЙСТВ ИСЧИСЛЕНИЙ 393 394 ч будучи не свойствами самих абстрактных ассоциативных систем, а лишь свойствами способов их задания. Учитывая, однако, что способ задания абстрактных ассоциативных систем посредством ассоциативных исчислений является ценным, алгебраист поставит вопрос об общих методах распознавания инвариантных свойств заданий. Этому вопросу соответствует следующая постановка нормальной массовой проблемы. Пусть Р— некоторое инвариантное свойство ассоциатив.
ных исчислений, а А — некоторый алфавит. Для ассоциативных исчислений в А мы введем, подобно тому как это в 942 делалось для нормальных алгорифмов, их изображения. Требуется построить нормальный алгорифм над двухбуквенным расширением алфавита А (одна буква требуется для отделения левых частей соотношений от правых и еще одна — для того, чтобы иметь возможность отделять соотношения друг от друга), применимый к изображению Й" всякого ассоциативного исчисления Й в А и перерабатывающий Й" в пустое слово тогда и только тогда, когда Й обладает свойством Р. Эту нормальную массовую проблему мы будем называть проблемой распознавания свойства Р для алфавипш А. Неразрешимость этой проблемы была доказана (А.
А. М а р к о в [7), [8[; см. также [9); полное изложение в монографии [2[, гл. У1, 9 11) при весьма общих условиях, налагаемых на Р и А. А именно, была доказана следующая теорема: 7.1. Пусть Р— инвариантное свойство ассоциативных исчислений. Если имеется как исчисление с этим свойством, так и исчисление, не включаемое ни в какое исчисление с этим свойством, то может быть указан алфавит, для которого проблема распознавания свойства Р неразрешима [в том смысле, что искомый в этой проблеме нормальный алгорифм невозможен). Если при этом алфавит исчисления со свойством Р состоит из и букв, то для всякого алфавита с числом букв, ббльшим и+3, проблема распознавания свойства Р неразрешима.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
