markov_teorija_algorifmov (522344), страница 58
Текст из файла (страница 58)
Множество М слов в алфавите А называют перечислимым в А, если существует нормальный алгорифм л)! над А такой, что для любого Р в А 81(Р) определено тогда и только тогда, когда Р 6М. Приняв эти определения, читатель без труда заметит, что если М есть множество слов в А, а алфавит Б есть расширение А, то М разрешимо (перечислимо) в Б тогда и только тогда, когда оно разрешимо (перечислимо) в А.
Таким образом, свойства множества быть разрешимым и быть перечислимым, по существу, не зависят от того, в каком алфавите это множество рассматривается, так что указание алфавита часто может быть опущено. Нетрудно показать, что 1.1. Всякое разрешимое множество слов является перечислимым. Теорема 3 48.2.4 означает, что 1.2. Существует перечислимое, но не разресиил!Ое множество слов в алфавите А„.
То, что фигурирующий в 1.2 алфавит состоит из двух букв, диктуется не существом дела, а лишь техническими деталями доказательства. Аналогичная теорема могла бы быть доказана и для однобуквенного алфавита, так что 1.3. Существует перечислимое, но не разрешил!Ое л!ножество натуральных чисел. 2. А теперь посмотрим, как в данных терминах выглядят другие результаты Я 47 и 48. Теорема 3 47.3.1 утверждает, что если алфавит А является расширением алфавита А„ то множество записей несамопримениллых нормальных алгорифмов в А неперечислимо. Тем более оно неразрешимо (теорема 3 47.4.2). Неразрешимо и множество записей сомоприменилгых нормальных алгорифмов в А (теорема Ч 47.4.3).
Мы предлагаем читателю показать, что оно тем не менее перечислимо. Теорема 4 48.2.1 фактически *) утверждает (читатель убедится в этом самостоятельно), что множество слов в А„ к которым неприменим алгорифм '1В, неперечислимо. Тем более оно неразрешимо. То же самое утверждается и о множестве слов в А„к которым неприменим алгорифм Ял (теоремы 3 48.2.2 и 3 48.2.3). О теоретико-множественной интерпретации теоремы 3 48.2.4 мы уже говорили. й 50. Конструктивный комментарий к Я 47 н 48 1.
Пусть Р— какой-либо одноместный вербальный предикат в алфавите А, Р— слово в этом алфавите, Рассмотрим дизъюнкцию "! см, яля сравненья ~ссрсму 1 3! 2,!, 3[4 ОснОВные теОРемы неВОзмОжности АлГОРиФмОВ [гл. ч? (1) «Р обладает свойством Р или неверно, что Р обладает этим свойством». Предположим, что эта дизъюнкция неверна. Тогда неверны оба ее члена, т. е., с одной стороны, неверно, что Р обладает свойством Г, а с другой стороны, неверно, что это неверно.
Следовательно, при любом Р наше предположение ведет к противоречию, и это означает, что 1.1. Каково бы ни было Р, неверно, что дизьюнкция (1) неверна. Это одна нз форм одного нз важнейших принципов так называемой ннтуиционнстской логики — «закона двойного отрицания „закона исключенного третьего"». Обычно этот принцип связывают с именем выдающегося голландского математика Л. Э. Я. Брауэра (1881 †19), впервые подвергшего в работе 111 острой и принципиальной критике взгляд на „закон исключенного третьего" как на логический принцип, имеющий универсальную применимость ").
В самом деле, в общем случае (т. е. когда предикаг Р произволен) мы не умеем указывать верный член дизъюнкции (1). А ведь именно это и требуется для того, чтобы признать ее истинной [см. 3' 7.11! Если же принять во внимание еще и параметрический характер этой дизъюнкции (она зависит от Р), то станет ясно, что для установления истинности высказывания (2) «каково бы ни было Р, верна днзъюнкция (1)», представляющего собой высказывание общности [см. 5 9], требуешься разыскать общий способ (алгорифм), указывающий по Р верный член дизъюнкции (1). Если конструктивную семантику высказываний общности мы построим так, чтобы искомый алгорифм требовалось предъявлять в уточненном виде (например, в виде нормального алгорифма), то при вполне определенном, конкретном предикате Р такой алгорифм может оказаться невозможным.
Тогда мы должны будем признать отрицание высказывания (2) истинным, а высказывание (2) ложным. Четыре примера таких предикатов мы можем почерпнуть вЯ47 и 48. Это следующие предикаты Р,— Р, со свободной вербальной переменной Р для слов в алфавите А„: ') Подробное изложение позиции Браузра читатель найдет н книге Л. Гейтинга [?1. ПРОВЛЕМА РАСПОЗНАВАНИЯ АННУЛИРОВАНИЯ 315 1'. Р,: «Р есть запись несамоприменимого нормального алга??Нфма в алфавите А,» (см. теорему 5 47.4.2); 2 . Р;. «Р есть запись самоприменимого нормального алгорифма в алфавите А,» (см, теорему 9 47.4.3); 3'.
Р,: «Нормальный алгорифм 2Б« неприменим к слову Р» (см. теорему 9 48.2.3); 4 . Р«. «Нормальный алгорифм ЯВ«применим к слову Р» (см. теорему 9 48.2.4). Дальнейшие примеры читатель сможет найти в последующем изложении. Читателю, не искушенному в конструктивной логике, конструктивно верные отрицания высказываний типа (2) покажутся, вероятно, „слишком экзотическими" (хотя на самом де- ле в них нет ничего парадоксального). Поэтому мы не будем упо треблять их в данной монографии, предпочитая вместо них пользоваться их расшифровками — утверждениями о невозможности соответствующих алгорифмов.
Тем не менее сам факт наличия таких высказываний является для конструктивной логики принципиальным. 9 51. Проблема распознавания аннулирования 1. Будем говорить, что алгорифм й аннулирует слово Р, если он перерабатывает Р в пустое слово. Аналогично проблеме распознавания применимости нормального алгорифма [9 48.11 может быть поставлена проблема Распознавания аннулирования слов нормальным алгоРифмом, состоящая в следующем.
Пусть дан нормальный алгорифм 0$ над алфавитом Г. Требуется построить нормальный алгорифм над Г, применимый ко всякому слову в Г н аннулирующий те и только те слова в Г, которые аннулирует 6. Мы покажем в этом параграфе, что алфавит Г и нормальный алгорифм Е в нем могут быть построены так, что проблема распознавания аннулирования слов в Г алгорифмом 91 будет неразрешимой. 2.
Докажем прежде всего следующую лемму: 2.1. Каков бы ни быт нормальный алгорпфм 9[ над алфавитом А, может быть построен нормальный алгорифм 5 над А, аннулирующий те и только те слова в А, к которым применим алгорифм Й. Пусть, В самом деле, 9?[ — нормальный алгорифм над алфавитом А. Пусть Б — его алфавит.
Построим нормальный алгорифм Сха в Б, аннулирующий всякое слово в этом алфавите [9 29.21. Определим алгорифм ?[) как нормальную СЛОЖНОСТНОй ПОДХОД 3!б ОснОВные теоремы неВОзможности ллГОРНФмОВ (гл ч! З(7 композицию алгорифмов й и чхвг (1) В= (6В ой) и покажем, что он является искомым нормальным алгорифмом над А, аннулирующим те и только те слова в А, к которым применим алгорифм й. Действительно, 2) есть нормальный алгорифм над Б [(1), 3 37.4.21, а так как Б очевидным образом является расширением А, то В есть нормальный алгорифм над А. Для любого Р в Б имеем, далее, (2) Ж (Р) Свв (31 (Р)).
Здесь й (Р) есть слово в Б, коль скоро алгорифм й применим к Р. следовательно, О:В (й (Р)) ~л прн том же условии. Условное равенство (2) показывает, таким образом, что алгорифм й тогда и только тогда применим к слову Р в Б, когда алгорифм Ж аннулирует это слово. Так как Б является расширением А, это и подавно справедливо для слов в А, что и требовалось доказать. 3. Теорема 3 48.2.2 и лемма 2.1 дают следующий результат: 3.1.
Может быть построен нормальный алгорифм 2Вг над алфавитном А„удовлетворяющий следуюи(ему условию: невозможен нормальный алгорифм над А„аннулирующий те и только те слова в А„которые алгорифм хглт не аннулирует. В самом деле, построим нормальный алгорифм ЯВе согласно 5 48.2.2 и применим к алфавиту А, и алгорифму лВа лемму 2.1. Согласно этой лемме постройм нормальный алгорифм лВ(, аннулирующий те и только те слова в А„ к которым применим алгорифм ХВе.
Согласно построению дг), тогда и только тогда не аннулйрует какое-нибудь слово в А„ когда алгорифм ЗВ, не применим к этому слову, откуда и следует, что ггВт есть искомый алгорифм. Теорема 3.1 допускает следующее усиление: 3.2. Может быть построен нормальньгй алгорифм 1ГВв в алфавите А„удовлетворяющий следующему условию: невозможен нормальный алгорифм над Л„оннулирующий те и только те слова в А„которые алгорифм аВз не аннулирует.
По сравнению с 3.1 усиление состоит в том, что 2В, строится как алгорифм в А„тогда как ЙВт строился как елгорифм над А,. Переход от 3.1 к 3.2 аналогичен переходу от 5 48.2.1 к 3 48.2.2; он осуществляется посредством построения перевода алгорифма глВз в алфавит А„что и дает искомый алгорифм ЯВ,. Подробное проведение доказательства теоремы 3.2 мы предоставляем читателю. Аналогично переходу от теоремы ~ 47.4.1 к теоремам ~ 47.4.2 и ~ 47.4.3 осуществляется переход от 3.2 к следующим результатам: 3.3. Может быть построен нормальный алгорифм глВ, в алфавипге А„удовлетворяющий следующему условию: невозлгожен нормальный алгорифм над А„применимый ко всякому слову в Л, и аннулируюи!ий те и только те слова в А„которьге 2(6., не аннулирует. ЗА.
Может быть построен нормальный алгорифм гВа в алфавите А„удовлетворлющии следующелгу условию. "невозможен нормальньгй алгорифм над А„прилгенимый ко всякому слову в Л, и аннулирующий те и только те слова в А„которые аннулирует 2гВв. Теорема 3.3 есть очевидное следствие теоремы 3.2, а теорема 3.4 легко доказывается на основе 3.3 с помощью РазветвлЯющего алгоРифма йв, лг е а (3 30.!1, где Б — алфавит предполагаемого алгорифма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
