markov_teorija_algorifmov (522344), страница 57
Текст из файла (страница 57)
Если А является расширением Лт, то невозлюжен норл!альный алгорифл! над А„применимый к записи Й' любого нормального алгорифма 1!Х в А и перерабатывающий ЗР в Л тогда и только тогда, когда Й самопри.Неким. В самом деле, допустим, что такой алгорнфм гт построен. Пусть Б — его алфавит. Тогда Б является расширением Л„ и потому а — буква Б.
Построим разветвляющий нормальный алгорифм ЙВ, л, А !3 30.11 и определим алгорифм ф как нормальную композипию алгорнфмов ХХТ и ЯВ ! а А. 3) ТТ (ЯВ, Л, а Лаа»). $ есть нормальный алгорифм над алфавитом Б ((З)1 и, следовательно, над А,, Условное равенство а1(!г) — Й В, 1, а, ! (а! ((Е)) 393 ОснОВные теОРемы неВОзмОжнОсти АлГОРНФмов !Гл. у! имеет место для любого 4',1 в Б и, в частности, (4) 9 (Й ) ~ 2(Б А а А (а (Я )) для любого нормального алгорифма й в алфавите А.
С дру- гой стороны, (5) Я Б, А, а, А (й (Й*)) Л. а ~(' Л если Я(й') ь Л [9 30 1(2)1, и (6) ЙБ, А а, А(М(й')) ~Л, если й(йа) в Л [9 30,1 (3)1, Так как алгорифм лг применим к записи любого нормального алгорифма в А, алгорифм 9 также применим к записи любого нормального алгорифма в А, причем 9(2Р) ХЛ тогда и только тогда, когда Я(2Р) е'.Л [(4) — (5)1 Но Я(йа) м Л тогда и только тогда, когда алгорифм й самоприменим. Следовательно, м' (ЯР) ф: Л тогда и только тогда, когда й несамоприменим. Значит, 9(4ТР) а Л тогда и только тогда, когда й несамоприменим. Невозможность нормального алгорифма 9 с этим свойством была, однако, только что установлена [4.2).
Следовательно, невозможен и нормальный алгорифм вг со свойством, указанным в теореме 4.3, что и требовалось доказать. $48. Проблема распознавания применимости алгорифма к исходному данному 1. В связи со всяким нормальным алгорифмом 6 над данным алфавитом Г естественно поставить проблему распознавания применимости этого алгорифма к словам в Г, состоящую в следующем: требуется построить нормальный алгорифм над Г, применимый ко всякому слову в Г и перерабатывающий в пустое слово те и только те слова в Г, к которым применим алгорифм 6.
Мы покажем в этом параграфе, что алфавит Г и нормальный алгорифм 6 в нем могут быть построены так, что проблема распознавания применимости алгорифма О! к словам в Г окажется неразрешимой: искомый в этой проблеме нормальный алгорифм будет невозможен. В основе построения будет лежать видоизмененная теорема об универсальном алгорифме, которую мы будем сочетать с результатами 9 47. 2. Пусть А, = аЬсйе. а 4В! ПРОБЛЕМА РАСПОЗНАВАНИЯ ПРИМЕНИМОСТР! 309 Дакажеь! следующую теорему: 2.1.
Может быть построен нормальный алгори4м 2В над ал4авитом Аа, удовлетворя4ощий следующему условию: невозможен нормальный1 алеори4л! м над А„перерабаты- вающий в Л те и только те слова в А„к которыл! Я) не применим. В самом деле, принимая во внимание, что буква е не принадлежит алфавиту Л„т. е.
аЬсй, построим нормальный алгорифм Я) над А,е, т. е. над А„согласно 9 45.5.1 та- ким образом, чтобы собл4одалось условие (1) 9В (ЯаеР) й (Р), А, играет при этом роль алфавита А из теоремы 9 45.5.1, е — роль 6; записи определяются для нормальных алгориф- мов в А,; (1) имеет место для слов Р в А, и нормальных алгорифмов Я в А,. Покажем, что ео удовлетворяет сфор- мулированному в теореме условию. Допустим, в самом деле, что Я есть нормальный алго- рифм над А„перерабатывающий в Л те и только те слова в Л„к которым 2В не применим. Построим тождественный нормальный алгорифм ЗА, в алфавите Л, [Ц 28.41.
Построим нормальный алгорифм 2) над алфавитом А„е согласно теореме объединения [2 38.1.11 таким образом, что (2) 6 (Р) ЗА,(Р)еЗА,(Р) для любого слова Р в алфавите А,. Построим, наконец, алгорифм 9 как нормальную компо- зицию алгорифмов Э и Й'. (3) 9 = — (ЛТР4В). 9 есть нормальный алгорифм над А,, так как Гс — нор- мальный алгорифм над А, [(3), 4 37.4.2]. Следовательно, 9 есть нормальный алгорифм над А,. Так как ЗА,— тож- дественный алгорифм в А„имеем, согласно (2), (4) 9) (9Р) ~ йаей' для любого нормального алгорифма й в А,.
Поэтому В (Йа),~ Я (ЯаеЯВ) и, следовательно, 9(2Р) мЛ тогда и только тогда, когда ааз (йа йа) ~ А С другой стороны, Ы(йае2Р) й (й') для любого нор- мального алгорифма й в А,[(1)1. Поэтому нормальный ал- 3!О ОСЕ!ОВНЫЕ ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИФМОВ !ГЛ. Ч! горифм 2( в А, тогда и только тогда несамоприменим, когда алгорифм !!8 не применим к слову й'ей'. Но, согласно нашему допущению, касающемуся алгорифма Й, 28 тогда и только тогда не применим к й'е2Р, когда Я(й'ей') ь Л, т. е. когда ф(21') ь Л. Таким образом, Ай(й')~Л тогда н только тогда, когда алгорифм й несамоприменим.
Алгорифм 9 с этим свойством, однако, невозможен согласно теореме 3 47,4,1, условие которой соблюдено, так как роль А играет А,. Тем самым установлена невозможность нормального алгорифма Я над А„перерабатывающего в Л те и только те слова в А„к которым алгорифм 28 не применим, что и требовалось доказать. Только что указанный алгорифм 28, удовлетворяющий условию, сформулированному в теореме 2.1, является нормальным алгорифмом в алфавите, состоящем из большого числа букв. Мы покажем сейчас, что уже в двухбуквенном алфавите А, может быть построен нормальный алгорифм с тем же свойством.
2.2. Может быть построен нормальный алгорифм 28, в алфавите А„удовлетворяющий следующему условию: невозя!Ожен нормальный алгорифм 9 над А„перерабатывающий в Л те и только те слова в А„к которым 28, не применим. Построим, в самом деле, нормальный алгорифм 28 над А, согласно 2.1 и нормальный алгорифм 28, в А„как перевод алгорифма 28 Ц 41,6], При этом роли А и Б пусть играют соответственно пустой алфавит и алфавит алгорифма 28. Очевидно, что Б является расширением А,.
Обозначая алгорпфм перевода через Х, будем для любого 1е в Б иметь 211! (т (! !)) — А (28 (Я)) Ц 41,6,26] причем л есть нормальный алгорифм над Б. Так как алгорифм А применим ко всякому слову в Б, это условное равенство показывает, что 28, тогда и только тогда применим к переводу слова 1е в Б, когда 28 применим к самому этому слову. 28„есть нормальный алгорифм в А,. Покажем, что он удовлетворяет условию, формулированному в 2.2. Допустим, действительно, что 9 есть нормальный алгорифм над А„перерабатывающий в Л те и только те слова в А„к которым 28, не применим.
ПРОБЛЕМА РАСПОЗНАВАНИЯ ПРИМЕНИМОСТИ 3! ! Построим алгорифм зт как нормальную композицию алгорифмов Х и $: (5) г! (АТояЬ). гс есть, как и Ь, нормальный алгорифм над Б 1(5), з 37.4.2] и, значит, над А,. Для любого !е в Б Я(В-ФД(Ц)) ((5), 4 37.4.3] и потому м(Я)ХЛ для тех и только тех слов Я для которых (6) !з (Ф (1е)) 3': Л. Здесь яь (!е) всегда является словом в А,. Поэтому, согласно предположению об алгорнфме 9, равенство (6) имеет место для тех и только для тех слов Я в А„для которых слово ь(9) таково, что алгорифм 28, к нему не применим. Применимость же 28, к т Я), как отмечено выше, равносильна применимости алгорифма 28 к 1е. Таким образом, нормальный алгорифм Й над А, перерабатывает в Л те и только те слова в А„к которым алгорифм 28 иене применим.
Такой нормальный алгорифм, однако, нвозможен 12.1]. Невозможен, следовательно, и нормальный алгорифм ф над А„перерабатывающий в Л те и только те слова в А„к которым алгорифм 28, не применим, что и требовалось доказать. Аналогично тому, как мы переходили от теоремы 3 47.4.1 к теоремам 3 47.4.2 и 3 47.4.3, можно перейти от теоремы 2.2 к следующим результатам. 2.3. Может быть построен нормальный алгорифя! 2!3, в алфавите А„удовлетворяющий следующему условию: невозможен нормальный алгорифм над А„применимый ко всякому слову в А, и перерабатывающий в Л те и только те слова в А„к которым 28, не применил!. 2.4. Может быть построен нормальный а !горифя! Ет), в алфавите А„удовлетворяющий следующему условию: невозмо жен нормальный алгорифм над А„применимый ко всяте и кому слову в А, и перерабатывающий в пустое слово е только те слова в А,, к которым 28, применим. Теорема 2.3 есть очевидное следствие теоремы 2.2, а теорема 2.4 легко доказывается на основе 2.3 с помощью Р азветвляющего алгорифма йв, А, „А, где Б — алфавит предполагаемого алгорифма з! '13 30.1].
! Во! КОНСТРУКТИВНЫЙ КОММЕНТАРИЙ з!з 3!2 ОСНОВНЫЕ ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИФМОВ !ГЯ. У! Теорема 2.4 показывает, что для некоторого нормального алгорифма 2Вл в А, проблема распознавания применимости к словам в А, неразрешима: искомый в этой проблеме нормальный алгорифм невозможен, $49. Теоретико-множественный комментарий к Я 47 и 48 Теорема 3 48.2.4 является одним из самых принципиальных результатов общей теории алгорифмов.
Из нее, в частности, могут быть извлечены отрицательные решения таких знаменитых массовых алгорифмических проблем математики, как проблема разрешимости для исчисления предикатов первой ступени (А. Ч е р ч [21; 1936 г.), проблема тождества для полугрупп (А. А. М а р к о в [51, [61 и Э. Л. ПО ст [21; 1947 г.), проблема тождества для групп (П. С. Н о в и к о в [11; 1952 г.), проблема гомеоморфии полиэдров (А. А.
М а р к о в [121, [131; 1958 г.), 10-я проблема Гильберта (Ю. В. М а т и яс е в и ч [2]; 1970 г.). Она выражает некий важный факт теории алгорифмов, обнаружившийся в 1936 г. в работах А. Ч е рч а [!1, [21, С. К. К л и н и [1] и А. М. Т ь ю р н н г а [11, [21. Мы изложили этот факт на языке нормальных алгорифмов. Теперь, учитывая интересы теоретико-множественно настро. енного читателя, мы изложим его и на языке теории множеств. При этом читателя, критически относящегося к концепциям теории множеств, мы просим иметь в виду, что мы придаем этому изложению лишь чисто эвристическое значение и что на приводимые ниже формулировки мы ни в каких доказательствах ссылаться не будем.
Данный комментарий, равно как и аналогичные комментарии в других параграфах (все они оговариваются особо), может быть механически изъят из книги без каких-либо последствий для остального ее содержания. 1. Множество М слов в алфавите А называют разрешимым в А, если существует нормальный алгорифм Й над А, проверяющий принадлежность слов в А к М. Эту формулировку можно уточнить следующим образом: требуется, чтобы алгорифм 81 был применим ко всякому слову в А и чтобы он перерабатывал в пустое слово те и только те слова в А, которые принадлежат М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
