markov_teorija_algorifmov (522344), страница 61
Текст из файла (страница 61)
Легко видеть, что для любого Р в А выполняется условие: !21(Р) тогда и только тогда, когда !5(Р). Кроме того, если Р в А и !Я(Р), то Я(Р)я.Л, Отсюда следует, что 2! пополним относительно А [1.2'), что и оставалось доказать. 3. Теоретико-множественный комментарий к теореме 1.1. Пусть А — алфавит, а М и У вЂ” какие- либо непересекающиеся множества слов в нем. Мы будем говорить, что М и У отделимы разрешимыми множествами, если существуют непересекающиеся разрешимые множества М, и У, слов в А такие, что М «= М, и У = Л',, Нетрудно показать, что для нормального алгорнфма (з, построенного в доказательстве теоремы 1.1, множества М, и Мь всех слов в алфавите А, таких, что й(Р)я.а и Й (Р) м Ь соответственно, перечислимы.
Вместе с тем они нв отделима разрешимыми л]ножеотвал]и. Покажем это. В самом деле, пусть У, и У„ †непересекающие разрешимые множества слов в алфавите А, такие, что М, «= У, и М„«: — У„. Пусть нормальный алгорнфм б над А, йроверяет принадлежность слов в А, к множеству У.. Это значит, что для любого Р в А,: 1) 0: (Р) определено и 2) (! (Р) ~ Л тогда и только тогда, когда Р Е У,. Пусть 3, и 3,— нормальные алгорифмы, для любого Р в А, удовлетворяющие условиям 2(1) и 2(2). Построим нормальный алгорифм В как нормальное разветвление алгорифмов,|, и йм управляемое алгорифмом 6: В = (3, ']' 3«! йг). Покажем, что В является пополнением 6 относительно А,. В самом деле, В полн относительно А„так как алгорифмы 6, 3, и 3ь применимы к любому слову в А,. Пусть теперь Р†сло в А, и б)(Р) определено.
Тогда Я (Р)я а или б](Р)ь«Ь. В первом случае РЕМ„, а значит, РЕУ„и потому (ь(Р) м. Л. Следовательно, в этом случае «] (Р) л«3, (Р), 329 ИЕПОПОЛНИМЫЙ АЛГОРИФМ з ьз] т. е. «] (Р) Ха. Во втором случае Р БМь и, значит, Р Е У,. Но У„и Уь не пересекаются, и потому Р(У„. Следовательно, ь (Р) )г Л и тогда В (Р) м 3ь(Р), т. е. «](Р) зе Ь. Итак, действительно, В является пополнением Й, что противоречит теореме 1.1. Значит, множества М„и М„не отделимы разрешимыми, что и требовалось доказать. Таким Образом, теорема 1.1 дает пример двух непересекающихся перечислимых множеств слон в алфавите А„не отде] лимых разрешимыми множествами. То обстоятельство, что эти множества у нас оказались множествами слов в двухбуквенном алфавите, обусловлено не существом дела, а техническими деталями доказательства: аналогичные множества могут быть построены и в однобуквснном алфавите, и тогда их можно рассматривать как обладающие соответствующими свойствами множества натуральных чисел.
Именно в таком виде этот результат и опубликован впервые в 1950 г. С. К. Кл и ни 13). Результат является аналогом известной теоремы П. С. Новикова о существовании двух В-неотделимых СА-множеств, и в 194б,'47 учебном году, ведя специальный семинар, посвященный выяснению аналогии между дескриптивной теорией множеств и теорией перечислимых множеств, П, С. Новиков излагал, в частности, и пример двух перечислимых множеств натуральных чисел, не отделимых разрешимыми.
К сожалению, относящиеся к этому кругу вопросов результаты П. С. Новикова остались неопубликованными (см. об этом на 277-й странице книги В. А. У с п е н с к о г о 12) и примечание редактора русского перевода В. А. Успенского на 277-й же странице книги С. К. К л и н и Я). ГЛАВА Ч!! ВЫЧИСЛИМЫЕ ВЕРБАЛЬНЫЕ ФУНКЦИИ ВЫЧИСЛИМЫЕ ВЕРБАЛЬНЫЕ ФУНКЦИИ зз! Поскольку алфавит А фиксирован, упоминания о нем в дальнейшем часто будут опускаться. Проиллюстрируем это определение на нескольких про. етых примерах. 1'. Нормальный алгорифм в А" со следующей сокращенно записанной схемой: В этой главе мы изложим некоторые факты общей теории алгорифмов, наиболее естественным образом формулируемые в терминах „алгорифмов от нескольких аргументов". Достаточно удобным техническим средством здесь может служить введенное в 5 24 понятие у-системы слов в алфавите А.
Буква у, однако, играет в у-системах двоякую роль: с одной стороны, она отделяет члены систем друг от друга, а с другой — заменяет „внешние скобки", и в сочетании с традиционной функциональной нотацией, где система аргументов функции заключается в скобки, употребление такого понятия системы привело бы к непривычной для глаза системе обозначений. Поэтому мы условимся отбрасывать у непустых у-систем окаймляющие их буквы у. Таким образом, вместо одночленной у-системы уРу у нас будет фигурировать слово Р, вместо двучленной у-системы уРу(~у — слово РЯ и т.
д. $ 54. Вычислимые вербальные функции 1. Мы будем считать фиксированным некоторый алфавит А, содержащий буквы а и в. Системы слов в этом алфавите мы будем рассматривать как слова в алфавите Ау с учетом только что сделанного замечания. Кроме того, мы добавим к Ау еще какие-нибудь две новые буквы а и (), чтобы иметь возможность произвольные нормальные алгорифмы над Ау трактовать как нормальные алгорифмы в алфавите Аару, который мы будем обозначать символом А+. Записи нормальных алгорифмов мы (обычным образом) определим именно для этого алфавита, так что, в частности, нормальные алгорифмы в А+ тоже смогут фигурировать в качестве значений аргументов вводимых ниже функций. Вычислимой вербальной функцией )Ч переменных ()Ч)1) в алфавате А мы будем называть любой нормальный алгорифм в алфавите А+, перерабатывающий всякую У-членную систему слов в алфавите А, к которой он применим, в какое-либо слово в алфавите А, которое и будет считаться значением функции на данной системе.
Я пробегает алфавит Ау) при любом )Ч)1 является вычислимой вербальной функцией Ж переменных. Ее значение на любой !Ч-членной системе слов равно пустому слову. 2'. Нормальный алгорифм в А+ со схемой при любом )Ч)1 является вычислимой вербальной функцией )Ч переменных. Эго — „нигде не определенная" функция.
3'. Нормальный алгорифм в А+ со схемой является вычислимой вербальной функцией одной переменной („тождественная функция"), но при 1Ч>1 этот алгорифм не является вычислимой вербальной функцией Ч переменных ( -за того, что при А!>1 в слове, являющемся результатом аб ет применения этого алгорифма к Ф-членнои системе, всегда уд присутствовать буква у). Говоря о вычислимых вербальных функциях (а в дальнейшем — и о вычислимых операторах над ними), мы иногда, в случаях громоздких словосочетаний, будем пользоваться эллиптизированной терминологией, сокращая часть употребляемого термина. Так, вместо «вычислимых вербальных функций» мы иногда будем говорить просто о «функциях».
В связи с этим мы хотели бы особо подчеркнуть, что вычислимая вербальная функция не есть функция, удовлетворяющая таким-то и таким-то ким-то условиям. Вычислимая вербальная функция— ым о нормальный алгорифм, подчиненный определенн эт ограничениям. Понятие это мы вводим без ссыл и к на какое-либо общее понятие функции, и обозначающий его термин должен восприниматься как единое слитное словосочетание, а не «через ближайший род и видовое отличиеж Мы специально отмечаем это обстоятельство ввиду того, что в литературе можно встретиться и с другим подходом, в рамках которого вычислимая вербальная функция одной переенной будет определяться как «такое отображение множества слов в себя, что его значения вычисляются при помощ и ВЫЧИСЛИМЫЕ БЕРБАЛЬНЫЕ ФУНКЦИИ !ГЛ.
ЧП некоторого алгорифма». Мы хотели бы четко отграничить наш подход от упомянутого ввиду тесной связи последнего с тео- ретико-множественной концепцией. Есть и еще один довод Б пользу нашего определения. Мы хотели бы, чтобы вычислимую функцию можно было (хотя бы в принципе) вычислять, чтобы было известно, как это де- лать. Йаше определение удовлегворяет этому требованию: вычислить значение вычислимой функции в какой-либо точ- ке — значит применить соответствующий нормальный ал- горифм к подходящему исходному данному. Что же касается только что сформулированного определения, то здесь дело обстоит не так просто.
В самом деле, пусть Ф вЂ” высказыва- ние, вопрос об истинности которого представляет собой нере- шенную математическую проблему (мы возьмем для конкрет- ности проблему Ферма). Определим арифметическую функцию ), положив для любого натурального У ~1, если Ф верно, г(Ф)- 10, если Ф неверно. Математик, принимающий «закон исключенного третьего», должен отнести эту функцию к вычислимым. Между тем ясно, что уже нахождение значения ) (О) равносильно решению про.
блемы Ферма. Аналогичную функцию можно определить и для любой другой „трудной" проблемы (неисчерпаемый источ- ник таких проблем дает любая неразрешимая нормальная массовая проблема). Нам представляется парадоксальным считать вычислимой всюду определенную функцню-констан- ту (ее значение равно 0 или 1), у которой не видно никаких подступов уже, например, к вычислению 1(0).
Разумеется, формального противоречия здесь нет, но есть известное рас. хождение с обычным словоупотреблением, в рамках которого суффикс «-им» несет определенную смысловую нагрузку. Занимая такую позицию, приходится игнорировать естест- венный, „обиходный" смысл этой языковой конструкции. Описанная ситуация носит общий характер. С аналоги- чными определениями мы встрегимся в дальнейшем, когда бу- дем рассматривать конструктивные действительные числа, конструктивные функции действительной переменной и т. д Все эти понятия будут вводиться самостоятельно, без каких- либо ссылок на соответствующие традиционные понятия. 2.
Рассмотрим один стандартный способ представления вы- числимых вербальных функций. Пусть Б — какой-либо алфавит, являющийся расшире- ..Лем алфавита Ау, Рассмотрим „фильтрующий" нормальный З»4 БЫЧИСЛИМЫБ ББРБАЛЬНЫВ ФУНКЦИИ 333 алгорифм 9Б, А в алфавите Б с сокращенно записанной схемой $ п обегает алфавит Б',А.
Легко видеть, что $Б, А пригде пр е меним к слову 9 в Б тогда и только д, тог а, когда оно есть слово в, пр А, ичем в этом случае выполняется графическое равенство 5Б, А ((г) Х (г ° П сть теперь 9 — какой-либо нормальный алгорифм"в Б. Рассмотрим нормальную композицию (5Б, А ) усть т МОВ 'С7 И фв, А. 9, . Для любой й(-членной системы Я слов в (ГГБ А о«)) (О) — 5Б А (5 (5)), оа) (3) так что в случае определенности выражения (6Б, А )( ) значение его есть слово в А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
