markov_teorija_algorifmov (522344), страница 68
Текст из файла (страница 68)
Построим, в самом деле, ассопиативное исчисление В над алфавитом А, согласно 2.1, т. е. так, чтобы соблюдалось условие: невозможен нормальный алгорифм над А„ перерабатывающий в пустое слово те и только те слова Р в А„ для которых эквивалентность 2(1) не имеет места. Покажем, что исчисление В является искомым. Действительно, пусть Б означает алфавит исчисления В. Тогда Б является расширением А„и потому Б является расширением йе, т. е. В есть исчисление над !(е. Доиустим, что $ есть нормальный алгорифм над Б, перерабатывающий в пустое слово те и только те слова в Б, которые не эквивалентны в исчислении В слову бей. Введем букву 6, не принадлежащую алфавиту Б, и построим нормальный алгорифм 6 в алфавите Бб, задав его схемой 6$ — $6 6- й йс6 ($ пробегает Б).
Нетрудно видеть, что (1) 6 (Р) Х йсрс( для всякого слова Р в Б. Построим теперь алгорифм Й как нормальную композицию алгорифмов (6 и,ф: (2) ьт — (9 ьб). Я есть нормальный алгорифм над Б и, значит, над А,. й(Р) ~$(6(Р)) (Р— слово в Б) [(2)~ ж$(с(сРс() (Р— слово в Б) [(1)~. Отсюда следует, что алгорифм Й тогда и только тогда аннулирует слово Р в алфавите А„когда алгорифм $ аннулирует слово с(сРй. Но $ тогда и только тогда аннулирует ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛРГРРПП 1гл. шн это слово, когда оно не эквивалентно в исчислении В слову бей. Таким образом, нормальный алгорифм Я над алфавитом А, перерабатывает в пустое слово те и только те слова в этом алфавите, для которых эквивалентность 2(1) не имеет места.
Такой алгорифм невозможен согласно построеинюисчисления В. Следовательно, невозможен и нормальный алгорифм $ над Б, перерабатывающий в пустое слово те и только те слова в Б, которые не эквивалентны в В слову бей, что и требовалось доказать. Пользуясь аналогичным образом теоремой 2.2, получаем следующий результат: 3.2. Может быть построено ассоциативное исчисление В над алфавитом йе, удовлетворяющее следующему условию: невозможен нормальный алгорифм над алфавитом исчисления В, применимый ко всякому слову в этом алфавите и перерабатывающий в пустое слово те и только те слова в нем, которые эквивалентны в В слову бей. 4. Установленная только что теорема 3.2 утверждает возможность построения ассоциативного исчисления В и некоторого слова В в его алфавите таким образом, что окажетсянеразрешимой следующая нормальная массовая проблема; построить нормальный алгорифм над алфавитом исчисления В, применимый ко всякому слову в этом алфавите и перерабатывающий в пустое слово те и только те слова в нем, которые эквивалентны в В слову В, Эту проблему мы будем называть проблемой эквивалентности слову В в исчислении В.
Следующая почти очевидная теорема устанавливает простую связь между проблемами этого типа и ранее определенными проблемами эквивалентности для ассоциативных исчислений [З 57.9]. 4.1. Если разрешима проблема эквивалентности для ассоциативного исчисления Й, то, каково бы ни было слово Я в его алфавите, разрешима и проблема эквивалентности этому слову в исчислении Й. В самом деле, пусть А — алфавит исчисления Й, Я— слово в А, гэ — нормальный алгорифм над АЖ, применимый ко всякому слову вида Р Ф Я, где Р н Я вЂ сло в А, и перерабатывающий такое слово в пустое слово тогда н только тогда, когда Й:РЯ Я.
Построим в алфавите АЖ нормальный алгорифм В правого присоединения слова ФТТ. Имеем (1) В (Р) хс Р Ф В. э БВ1 НЕРАЗРЕШИМОЕ АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ Зб7 Построим алгорифм эг' как нормальную композицию алгорифмов В и ф: (2) гт — ($ ь В). Я есть нормальный алгорифм над А, причем для любого слова Р в А (3) Й(Р) 9(В(Р)) (Р— слово в А) [(2)] 9(Р Ф)7) (Р— слово в А) [(1)]. Так как алгорифм $ применим ко всякому слову вида Р Ф Я, где Р и Я вЂ” слова в А, алгорифм гг применим ко всякому слову в А [(3)]. Из (3) следует далее, что й тогда и только тогда аннулирует слово Р в А, когда (р аннулирует слово Р Ж Я. А это имеет место тогда и только тогда, когда Й: Р~Я К.
Таким образом, Я! есть нормальный алгорифм над А, применимый ко всякому слову в этом алфавите и перерабатывающий в пустое слово те и только те слова в нем, которые эквивалентны в Й слову Я. Тем самым проблема эквивалентности слову Я в исчислении Й решена и теорема доказана. Как непосредственное следствие из 4.1 получаем 4.2. Пусть ассоциативное исчисление Й таково, что для некоторого слова в его алфавите неразрешима проблема эквивалентности в Й этому слову. Тогда проблема эквивалентности для Й неразрешима. Как следствие из 3.2 н 4.2 получаем 4.3.
Может быть построено ассоциативное исчисление, для которого проблема эквивалентности неразрешима. Эта теорема допускает следующее уточнение: 4.4. Может быть построено ассоциативное исчисление В в некотором, не содержащем звездочку алфавите Б, удовлетворяющее следующему условию: невозможен нормальн й алгорифм над БЖ, перерабатывающий в пустое слово те и только те слова вида Рэка (Р и Я вЂ” слова в Б), для которых эквивалентность В:Р][Я не имеет меспи. Эта теорема доказывается совершенно аналогично 4.3. Надо лишь воспользоваться 3.1 вместо 3.2 и применить алгорифм правого присоединения слова яч(ей, связывающий алгорифмы, о которых говорится в 4.4, с алгорифмами, о которых говорится в 3.1. Имея в виду истолкование проблемы эквивалентности для ассоциативного исчисления как проблемы тождества для поро- 368 ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП [ГЛ.
ЧП1 ждаемой им К-системы [9 57.91, мы можем истолковать теорему 4.3 как теорему о возможности построения К-системы с неразрешимой проблемой тождества. 5. В теореме 4.3 лишь утверждается возможность построения ассоциативного исчисления, но не выписывается определяющая система такого исчисления в явном виде. Теоретически такая система соотношений может быть, правда, получена на основе всего предыдущего. Для этого нам пришлось бы, проследив весь ход рассуждений, приведший нас к теореме 4.3, конкретизировать его в том смысле, что схемы всех применявшихся нормальных алгорифмов выписывались бы в явном виде. В частности, нам пришлось бы конкретизировать схему видоизмененного универсального алгорифма е[) для алфавита А! в роли А и буквы е в роли б [9 48.2.11; мы затем должны были бы построить схемы нормальных алгорифмов »1Вв [9 48.2.21, »««11 [5 48.3.11 и ЙВв [9 51.3.21. Исходя, наконец, из схемы алгорифма ЧВв н применяя построение, указанное в доказательстве теоремы 1.1, мы получили бы схему искомого ассоциативного исчисления.
Ясно, что в результате получилось бы нечто весьма громоздкое. А так как проблема явного и возможно более простого задания ассоциативного исчисления с неразрешимой проблемой эквивалентности представляет несомненный интерес, хотя бы в качестве возможной основы для проведения других построений, следует искать другие пути ее решения. Один из таких путей был пройден в гл. И монографии А.
А. М а р к о в а [21, где было построено ассоциативное и нслепие 6, в тринадцатибуквенном алфавите аьсае)й[[1[й[т со следующей сокращенно записанной схемой: ьв[ «-»т[ь е$ +$е е$ «-»$е $т«-»$п пЕ9 «-» $8 $8Д «-» д$ «[! «-»«[Ь !«[<-»Ф Ьс++ сд. Здесь $ пробегает двухбуквенный алфавит аь, Ь вЂ” четырехбуквенный алфавит аьс«[, а т[ — пятибуквенный алфавит 11151, $581 НЕРАЗРЕШИМОЕ АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ причем 369 а 8, Ь а=А, Ь вЂ” 1. В этом исчислении неразрешима проблема эквивалентности некоторому фиксированному (правда, очень длинному) слову, способ построения которого указан.
Определяющая система исчисления 6, состоит из 33 соотношений: первая строка охватывает 28 соотношений, следующие пять — по два. Там же А. А. Марков показал, что если к определяющей системе исчисления 6, добавить четыре соотношения ь)еат ++ 7еат $ пробегает алфавит аьс«[), то это даст новое ассоциативное исчисление б„у которого будет неразрешима проблема эквивалентности слову 1еат, б.
Приведем следующие „рекордные" результаты: 1'. Г. С. Ц е й т и н [11 (подробное изложение в [21) доказал неразрешимость проблемы эквивалентности некоторому фиксированному слову для ассоциативного исчисления в пяти- буквенном алфавите аЬс«[е со следующей простой определяющей системой соотношений: ( ас«-»са а«[+-ь «[а Ьс++ сЬ Ы «-» «[Ь еса «-» се е«[ь «-» «(е сса++ ссае У ассоциативного исчисления (в том же алфавите) с не сколько более сложной определяющей системой ас++'са Ьс «-»„сь ьд «(ь есав++'„се е«(ь,'«-»»4е с«[са о» с«(сае сааа «-» ааа дааа+-»,'ааа неразрешима проблема эквивалентности слову ааа.
[3 А А. Мврвов.'Н, М. Нвгорный пРОБлемА тождестВА для пОлуГРупп пл. шп 370 1 БВ1 пРОБлемА экВНВАлентности пустому слОВу 371 2'. Ю. В. М а т и я с е в и ч [11 построил пример ассоциативного исчисления в двухбуквенном алфавите с определяющей системой из трех соотношений, имеющего неразрешимую проблему эквивалентности некоторому фиксированному слову. У этого исчисления два соотношения из трех просты. Длины левой и правой частей третьего соотношения равны соответственно 304 и 608.
Вопрос о возможности дальнейшего уменьшения числа соотношений пока остается открытым. 3'. Соотношение Т+-~ (7 называется несократимым, если наибольшее начало и наибольший общий конец слов Т и [7 являются пустыми. С. И. А д я н [3) построил алгорнфм, решающий проблему эквивалентности для любого ассоциативного исчисления, определяемого одним несократимым соочношением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
