markov_teorija_algorifmov (522344), страница 64
Текст из файла (страница 64)
гллвд ип ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП (ПРОБЛЕМА ТУЗ) В гл. Ч1 была установлена неразрешимость некоторых нормальных массовых проблем, естественно возникающих внутри теории алгорифмов. Эти результаты открывают возможность перейти к установлению неразрешимости целого ряда массовых алгорифмических проблем, относящихся к традиционным разделам математики таким, как алгебра, топология, математический анализ. Рассматриваемыепри этом проблемы, естественно, должны пониматься как нормальные массовые проблемы, т. е, как проблемы разыскания нормальных алгорифмов, позволяющих распознавать те или иные свойства изучаемых объектов. В этой главе мы рассмотрим одну из наиболее известных и естественных проблем такого рода в алгебре — проблему тождества для полугрупп. Центральный результат главы фактически будет заключаться в построении примера конечно определенной (т.
е. заданной конечным числом образующих элементов и определяющих соотношений) полугруппы с неразрешимой проблемой тождества. Понятие конечно определенной полугруппы допускает простую и естественную конструктивизацию в виде понятия ассоциативного исчисления. Рассматриваемая нами проблема тождества при этом трансформируется в проблему эквивалентности для ассоциативных исчислений. Проблема эта была сформулирована еще в 1914 г. норвежским математиком Акселем Т у э [11. Самому Туэ удалось решить ее лишь в весьма частных случаях. Дальнейшие попытки найти общее решение этой проблемы, несмотря на усилия известных математиков, не привели к успеху, и причина этого обстоятельства впоследствии стала ясна: оказалось, что могут быть построены конкретные примеры ассоциативных исчислений, для которых эта проблема неразрешима. Первые примеры таких исчислений были одновременно и независимо опубликованы в 1947 г.
А. А. М а р к о в ы м [51, [6[ и Э. Л. П о с т о м [21. Тем самым был указан первый пример „внутриматематическойч неразрешимой массовой алгорифмической проблемы. С течением времени была установлена неразрешимость и других известных проблем этого рода. В первую очередь упомянем проблему $ >н АССОЦИАТИВНЫЕ ИСЧИСЛЕНИЯ 345 344 пРОьлемз тождест!>А лля полуГРупп ГГЛ ЮП тождества для групп (П. С. Н о в и к о в [1], [2]), проблему гомеоморфии полиэдров (А. А. М а р к о в [12], [13]), 1О-ю проблему Гильберта (]О. В.
М а т и я с е в и ч ]2)). В настоящей главе решение упомянутой выше проблемы тождества осуществляется на основе излагаемой в этой книге теории нормальных алгорифмов. Исторически, однако, дело обстояло несколько иначе. А именно, понятие нормального алгорифма как раз и возникло в процессе поисков возможно более простого изложения решения этой проблемы.
$57. Ассоциативные исчисления 1. Допустим, что знак «4-»> не является буквой алфавита А. Соотношением в алфавите А будем тогда называть всякое слово в алфавите А «-+ вида (1) Т .—> О, где Т и [> †сло в А. В частности, (2? есть соотношение в А. Слово Т мы будем называть левой частью соотношения (1), слово 0 — его правой частью.
2. Определим теперь понятие «ассоциативного исчисления>. Это понятие будет иметь много общего с понятием нормального алгорифма. Существенное различие будет, однако, состоять атом, что в то время, как всякий алгорифм является некоторым предписанием действовать в точности так-то и так-то и в такой-то последовательности, ассоциативное исчисление будет не предписанием, а лишь разрешением производить такие-то действия.
При этом таких разрешенных действий будет обычно несколько и на выбор того или иного из них не будет накладываться никаких ограничений. 3. Аналогично нормальному алгорифму всякое ассоциативное исчисление будет связано с некоторым алфавитом. Подобно тому, как существенной составной частью нормального алгорифма является его схема, т.
е. система его формул подстановок, существенной составной частью всякого ассоциативного исчисления будет являться его «определяющая система»вЂ” некоторый список соотношений в алфавите исчисления, В отличие от того, что имеет место для формул схемы нормального алгорифма, порядок соотношений в определяющей системе Р тг РТЕ, Я ~РУЯ (1) (2) ассоциативного исчисления не будег иметь существенного значения. 4. Пусть имеем некоторый (быть может, пустой) список соотношений С в алфавите А. Будем называть допустимыми относительно Й действиями следующие действия над словами в А: 1) подстановку вместо любого вхождения левой части одного из соотношений, принадлежащих Я, правой части того же соотношения; 2) подстановку вместо любого вхождения правой части одного из соотношений, принадлежащих (Б, левой части того же соотношения.
Ассоциативным исчислением в алфавите А, определяемым системой Ж, будем называть разрешение последовательно производить, исходя из любого слова Р в А, любые дейвия, допустимые относительно (Б. Обо всех словах, которые будут при этом получаться, включая само исходное слово Р, будем говорить, что они эквивалентны Р в рассматриваемом ассоциативном исчислении. Всякое ассоциативное исчисление определяется, таким образом, некоторым алфавитом — алфавитом этого исчисления — и некоторой (быть может, пустой) системой соотношений в этом алфавите — определяющей системой этого исчисления. Мы будем говорить об ассоциативном исчислении Й, что оно есть ассоциативное исчисление над алфавитом А, если алфавит этого исчисления есть расширение А.
5. Пусть «4 — ассоциативное исчисление в алфавите А, определяемое системой соотношений (5. Будем говорить, что слово 9 в А смежно со словом Р в исчислении л, если Я может быть получено из Р в результате одного действия, допустимого относительно ю. Предполагая, что знак «!» не есть буква алфавита А, будем пользоваться этим знаком для обозначения смежности слов в ассоциативных исчислениях в этом алфавите.
В дальнейшем запись 2[: Р 1 будет означать, что ]41смежно с Р в ассоциативном исчислении 2[. Следующие утверждения непосредственно вытекают из определения смежности: 5.1. Если Р и 14 — слова в алфавите ассоциативного исчисления 21, то Й: Р[ 9 тогда и только тогда, когда существуют такие слова ?[>, Я, Т, 1>', что 346 !'РО!!ЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП [гл. шп и что хотя бь! одно иэ соотношений (3) Т «-«и, (4) и <-~т принадлежит определяющей сисгпеме исчисления Й.
5.2. Если Й: Р ! Аг, то Й: (г ) Р. 5.3. Если Й: Р 1 Я, то Й: !«Р 1 !т!г и Й: Р)А! ! Щ для всякого слова 1« в алфавите исчисления Й. 6. Пусть Й вЂ” ассоциативное исчисление в алфавите А, и пусть у †бук, не входящая в А. у-систему Я слов в алфавите А мы будем называть Й-рядом, если всякий раз, когда слово Х в алфавите А соседствует в Я слева со словом )' в этом же алфавите, т. е. когда слово уХу)'у входит в Я, имеет место смежность Й: Х ! Г.
Пусть Р и () — слова в алфавите А. Мы будем говорить, что Р эквивалентно Я в исчислении Й, если может быть построен Й-ряд Я, соединяющий Р с Я, т. е. такой, что Р есть первый, а Я вЂ” последний член Я. Предполагая, что знак «Я > не является буквой алфави- тов рассматриваемых ассоциативных исчислений, мы будем пользоваться этим знаком для обозначения эквивалентности в этих исчислениях. В дальнейшем запись (!) Й: Р!)Я будет обозначать, что 9 эквивалентно Р в ассоциативном исчислении Й.
Следующие утверждения очевидны: 6.1. Если Й: Р1Я, то Я; Р3 9. 6.2. Й: РЯ Р для всякого слова Р в алфавите ассоциа- тивного исчисления й. 6.3. Если й: Р !) 1;1, то Й: 9 $ Р. 6.4. Если Я: Р !)Я и Й; 1г !) 1«, то й: РЯ Рт. С помощью 5.3 легко доказывается следующее утверж- дение: 6.5.
Если й: Р$Я, то Й: !«Р$ Щ и й: РК$ Щ для всякого слова !с' в алфавите исчисления Й. С помощью 6.4 и 6.5 доказывается 6.6. Если Й: Рй Я и Й: )Ц О, то Й; РЙЗЯЬ. 7. В литературе встречается другое определение ассо- циативного исчисления, по существу равносильное сформу- лированному выше. Оно состоит в следующем. Будем опять рассматривать систему соотношений в в алфавите А. Ассоциативным исчислением в алфавите А, оп- ределяемым системой Я, будем называть разрешение после- АССОЦИАТИВНЫЕ ИСЧИСЛЕНИЕ 347 довательно производить, исходя из соотношений системы Я и соотношения 1 (2), следующие действия, порождающие новые соотношения в А: 1) переход от какого-либо уже имеющегося соотношения 1(1) к соотношению где з — любая буква алфавита А; 2) переход от какого-либо уже имеющегося соотношения 1(1) к соотношению (2) т5 и~, где $ — любая буква алфавита А; 3) переход от каких-либо уже имеющихся соотношений 1 (1) и (3) Т«-«)! к соотношению (4) и В отличие от определения ассоциативного исчисления, данного в п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
