markov_teorija_algorifmov (522344), страница 71
Текст из файла (страница 71)
В дальнейшем основной интерес для нас будут представлять бинарные отношения типа эквивалентности, т. е. рефлексивные, симметричные и транзитивные. Рассмотрением именно таких отношений мы и ограничимся. 2. Итак, пусть Я вЂ” какое-либо бинарное отношение рассматриваемого типа. Нормальный алгорифм 3 над алфавитом А мы будем называть вычислимым инвариантом этого отношения, если 3 применим ко всякому слову в А и перерабатывает всякие два слова, связанные этим отношением, в одно и то же слово. Мы будем говорить, что вычислимый инвариант 3 отличает слова Х и 1', если 3 (Х) ф: 3 (К). Два слова Х и )' мы будем называть неотличимыми по инварианпи!м отношения Я, если для любого вычисли- мого инварианта 3 этого отношения имеет место графическое равенство Разумеется, всякие два слова, связанные отношением Я, неотличимы по инвариантам этого отношения. Обратное, как мы впоследствии убедимся, верно не всегда.
3. Со всяким бинарным отношением Я естественным образом связывается массовая алгорифмическая проблема 3'е ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП |ГЛ У|И распознавания тех пар слов Хх«)', у которых Х и 1' свя- заны отношением 31, Сравнительно нетрудно показать, что 3.1. Если проблема б|щ разрешима в том смысле, что может быть указан решающий ее нормальный алгорифм, то может бь|ть построен вычислимый инвариант Зщ отно- шения 91, о»т|личающий любые не связанные этим отноше- нием слова Х и 1'. Оставляя детали построения читателю, мы ограничимся изложением одного только общего плана требующейся здесь конструкции, Сначала мы каким-либо «хорошим» способом распола- гаем слова в алфавите А в вычислимую последовательность.
(Например, можно выписывать слова в порядке возраста- ния их длин, а при равных длинах — в лексикографичес- ком порядке,) Инвариант Зщ мы будем строить так, чтобы он прини- мал в качестве значений натуральные числа и чтобы он был неубывающем функцией своего аргумента. Первому члену построенной нами последовательности слов в алфавите А мы ставим в соответствие число О.
Пусть теперь 1»' — натуральное число, большее единицы, и пусть значения Вщ определены для всех членов последо- вательности с номерами, меньшими |ч'. Значение Вщ на г»'-м члене последовательности мы зададим следующим образом. Пользуясь (нормальным) алгорифмом, решающим проблему б|щ, мы выясним, имеются ли среди членов последователь- ности, предшествующих Ф-му, такие, которые связаны с ним отношением 31. Если таких членов нет, мы увеличи- ваем значение Зщ по сравнению с предшествующим на еди- ницу.
Если же такие члены лмеются, то мы берем в ка- честве вновь определяемого значения Зщ его значение на первом из таких членов. Оформив построенный таким образом алгорифм в виде нормального (соответствующая возможность подсказывается принципом нормализации), мы затем без особого труда установим, что он является вычислимым инвариантом отно- шения И и что он обладает свойством, указанным в фор- мулировке теоремы 3.1. Таким с»бразом, для того чтобы доказать неразрешимость проблемы З'щ, достаточно указать слова Х и У, не связан- ные отношением 81, но не отличимые по его инвариантам. 4.
С л»обым ассоциативным исчислением естественным образом си|язывается некоторое рефлексивное, симметричное э 60! МЕТОД ВЪ|ЧИСЛИМЫХ ИНВАРИАИТОВ зет Положим Х вЂ” паап, У ПОЬИ (1) (2) и покажем, что исчисление В и слова Х и Г в его алфавите удовлетворяют условиям 1' и 2'. Дей|твительно, допустим, что В:Х(1), т. е.
что (3) В: поал Е ПОЬП 1(1), (2)1. Пусть Р— какое-либо слово в А„. Предположим, что Е применим к Р. Тогда в силу выбора 6 либо (А)(Р)2:а, либо Е(Р)Х5. Допустим, что 81(Р) за. Тогда (4) В: нрРИ )( паап. Но имеет место эквивалентность (3), и, значит, В: пррп 11 пабп ((4), (3)1, и транзитивное бинарное отношение — отношение эквивалентности слов в этом исчислении, и, следовательно, можно говорить о вычислимых инвариантах этого отношения.
Мы покажем сейчас, что имеет место 4.1. Могут быть построены ассоциативное исчисление В и слова Х и 1' в его алфавите таким образом, что будут соблюдены следующие условия: 1'. Х и 1 неэквивалентны в В. О« 2 . Х и 1' неотличимы по инвариантам отношения эквивалентности слов в В. В самом деле, возьмем построенный для доказательства теоремы Э 53.1.1 нормальный алгорифм Е над алфавитом А, такой, что: 1) всякий раз, когда Ф применим к какому- либо слову Р в А„, |з(Р)~а или 6(Р) агу и 2) Ю непополним относительно А,.
Пусть à — алфавит алгорифма Э, а буквы и, р и а отличны друг от друга и не принадлежат Г. Применим к 6 теорему ь«58.1.1 и построим, согласно этой теореме, ассоциативное исчисление В над алфавитом Гира таким образом, чтобы равенство Е(Р)~ |г для слов Р и 9 в алфавите Г выполнялось тогда и только тогда, когда имеет место эквивалентность В: прРП )) па|гп. зан пРОБлемы РАспОзнАВАния сВОйстВ исчислениЙ 339 388 ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУГП! !ГЛ. Чп! А тогда 6)(Р)жЬ, и потому ажЬ, что неверно.
Следова- тельно, равенство Е (Р)АГ а невозможно. Аналогично, невозможно и равенство Е (Р) лкЬ. Значит, алгорифм 6) не применйм ни к какому слову Р в А,, а тогда он пополним относительно А, 1см. 6 53 1.1'], что противоречит выбору 6). Значит, условие 1а теоремы 4.1 соблюдается. Проверим теперь условие 2'. Пусть 3 †как-либо вычислимый инвариант отношения эквивалентности слов в кВ, и пусть слова 3 (паап) и 3(яаЬП) различны. Пользуясь теоремами сочетания, и, в частности, теоремой разветвления, построим е) нормальный алгорифм В над алфавитом А, таким образом, чтобы для любого слова Р в Татом алфавите выполнялось графическое е*) равенство (5) В (Р) тг 1 а, если 3(прРП)тг3(ппап), ] Ь, если 3(прРП) ~У 3(поап).
Алгорнфм В применйм к любому слову в А„и, значит, он полн относительно А,. Пусть теперь (6 применим к Р в А,. Тогда либо 6) (Р) йа, либо 6)(Р) ХЬ. Допустим, что 6) (Р) д а. Тогда 6): прРП Я ппап, и, значит, (6) 3 (прРп) Х 3 (поап), а потому В(Р) й.а 1(5), (6)] н В(Р) йЕ(Р). Допустим, что 6)(Р) мЬ. Тогда )О: прРП аегиГЬП, и, значит 3 (прРП) Ас 3 (ппЬП).
Но 3(ппЬП) ~У:3(поап), и потому (Т) 3 (прРП) ~' 3 (паап), так что В(Р)'Б Ь 1(5), (7)] и В(Р) йб)(Р). Таким образом, алгорифм В является пополнением 9 относительно А„ что противоречит выбору 6). *) Детали построения мы аставляемчнтателю, рассчнтывая нанакопнвшнйся у него опыт. ее) Обращаем внимание на то, что алгорнфм 3 прнменйм ко всякому слову в алфавите Гпра., Следовательно, слова 3(поап) и 3(ППЬП) не могут быть различными, 'и так как инвариант 3 произволен, то слова поап,'и поЬп, т. е.
Х и )', неотличимы по инвариантам отношения эквивалентности слов в я), что и оставалось доказать. 3 а м е ч а н и е. Сказанное в конце и. 3 позволяет заключить, что проблема эквивалентности для исчисления 6 неразрешима, и в этом смысле теорема 4.1 является усилением теоремы 9 58.4.3. Правда, неизвестно, является ли это усиление существенным.
Н. М. Н а г о р н ы м [51 построен пример перечислимого, но неразрешимого 1см, 949.11 бинарного отношения эквивалентности слов, у которого любые два слова, не связанные этим отношением, отличимы по его инвариантам. Вопрос о возможности получения аналогичного результата для отношений эквивалентности в ассоциативных исчислениях остается открытым. 6 61. Проблемы распознавания свойств ассоциативных исчислений Как мы уже отмечали, с алгебраической точки зрения ассоциативные исчисления — это способы задания ассоциативных систем. Свойства ассоциативных систем, возникающие в результате разного рода алгебраических классификаций, естественным образом порождают соответствующие им свойства ассоциативных исчислений. Естественно интересоваться массовыми алгорифмическими проблемами распознавания этих свойств.
В данном параграфе мы изложим один общий результат, касающийся проблем распознавания таких свойств. К сожалению, за недостатком места мы будем вынуждены придать изложению конспективный характер, ограничившись ссылками на литературные источники, содержащие полные доказательства приводимых утверждений. 1.
Пусть Я и 5 — ассоциативные исчисления в алфавитах А и Б соответственноа О нормальном алгорифме 1е над алфавитом А () Б мы будем говорить, что он есть еомоморфизм Я в В, если он удовлетворяет следующим условиям: Г.1. Всякое слово в алфавите А алгорифм кз перерабатывает в некоторое слово в алфавите Б. Г.2. Гели 6(: РЯ Я, то 6): В(Р) ]) 6Щ). Г.З. Для любых Р и (г в А имеет место эквивалентность 2): ~( ЕЛ ~(Р)а(Е, пРОБлемА тождествА для ПОЛРРРРпп гьгг ПРОБЛЕМЫ РАСПОЗНАВАНИЯ СВОЙСТВ ИСЧИСЛЕНИЙ ззг 1гл, чнг Легко доказывается следующая теорема: 1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
