книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

Своеобразной чертой конструктивного анализа яв­ ляется акцентирование внимания на вопросах эффек­ тивности, изучение вводимых объектов (а рассматри­ ваются лишь конструктивные объекты) как исходных данных алгорифмов. Эта специфическая точка зрения приводит иногда к необычным для традиционного ана­ лиза ситуациям, в частности, к «расщеплению понятий». Приведем несколько примеров.

A) КПРЧ а назовем псевдофундаментальной, если Vn ~] "] 3mV// (l, }>mz3 \ а (/) - а (/) | < 2"").

Как введенное выше понятие фундаментальной КПРЧ, так и это понятие укладываются в классическую концеп­ цию фундаментальности. Конструктивно же эти два по­ нятия различны: можно построить псевдофундаменталь­ ную КПРЧ, для которой невозможен регулятор фунда­ ментальности (поскольку, как легко видеть, всякая мо­ нотонная ограниченная КПРЧ псевдофундаментальна, то искомый пример дается уже упоминавшимся резуль­

КДЧ дают одну и ту же концепцию вычислимого дей­ ствительного числа. Ясно, однако, что КДЧ как кон­ структивный объект гораздо «информативнее», чем /••-число: наряду с последовательностью рациональных приближений из КДЧ извлекается и эффективная оценка скорости сходимости этой последовательности. Как по­ казал Г. С. Цейтин, алгорифм, находящий для каждой фундаментальной КПРЧ ее регулятор фундаментально­ сти, невозможен; поэтому отсутствующая в /•'-числах ин­ формация не может быть эффективно восстановлена. Из сказанного вытекает неравноценность ^-чисел и КДЧ как исходных данных для алгорифмов, что делает есте­ ственным их конструктивное различение.

B) Будем говорить, что КДЧ л; является пределом конструктивной последовательности КДЧ (сокращенно КПДЧ) а, если а сходится к х (см. стр. 41). Согласно уже упоминавшейся теореме о полноте конструктивного континуума для каждой фундаментальной КПДЧ а су­ ществует КДЧ, являющееся ее пределом. В традицион­ ной математике эта теорема является достаточным ос-

нованием для введения оператора, переводящего всякую фундаментальную КПДЧ в ее предел. Вместе с тем ана­ лиз доказательства теоремы о полноте показывает, что при построении предела КПДЧ используется и ее регу­ лятор фундаментальности — конструктивная расшифров­ ка данной теоремы (ср. п. 7), учитывающая это обстоя­ тельство, состоит в осуществимости алгорифма у, пере­

ляющееся пределом а. Упомянутый же выше оператор предельного перехода оказывается невычислимым; осу­ ществляющий его алгорифм невозможен из-за недоста­

(оператор предельного перехода) являются часто свое­ образными источниками неэффективности в традицион­ ном анализе. Изучение подобных ситуаций с алгорифмической точки зрения приводит к появлению специфиче­ ских наборов исходных данных, обеспечивающих алгорифмическое выполнение тех или иных операций (такой характер носят сами КДЧ, рассмотренные только что

Конструктивные теории дают ясную картину вычис­ лительных связей в анализе; доказываемые здесь тео­ ремы невозможности алгорифмов (подобные результаты совершенно отсутствуют в традиционных курсах ана­ лиза) выявляют потенциальные вычислительные тупики, представляемые некорректно поставленными алгорифмнческими задачами, а сопоставление этих теорем с поло­ жительными результатами о существовании алгориф­ мов, находящих искомые объекты по более полным дан­ ным, позволяет достичь отчетливой ориентировки в во­ просе о том, какие исходные данные необходимы для эффективного построения тех или иных объектов ана­ лиза. Можно надеяться, что интенсивно развивающаяся в настоящее время теория сложности алгорифмов и вы­

конце п. 1), можно констатировать, что при сравнении конструктивного и традиционного анализа имеется ши­ рокий спектр возможностей — от почти полного совпаде­ ния целых разделов до фактического отсутствия анало­ гий. При этом различия относятся, главным образом, к общим свойствам основных понятий; при использова­ нии же этих понятий в конкретных вычислительных си­

вопросов (1), так и в круге вопросов (2) (п. 1). Мы ста­ рались учесть интересы соответствующих категорий чи­ тателей, расценивая при этом категорию читателей, ин­ тересующихся вопросами (2), как более многочисленную. В этой связи мы отказались от «пересказа» ряда разде­ лов анализа (таких, как теория рядов, элементарные и специальные функции и т. д.), где конструктивное изло­ жение сравнительно слабо отличается от традиционного, а также от использования сколько-нибудь развитой системы конструктивной логики. Читатель, не интере­ сующийся философско-методологической стороной дела, может, пренебрегая возможными «граничными эффекта­ ми», практически считать, что излагаемая теория вло­ жена в традиционный анализ. При такой точке зрения конструктивные действительные числа и функции стано­ вятся частными случаями соответствующих классических понятий; в некоторых их необычных свойствах также не оказывается при ближайшем рассмотрении ничего пара­ доксального. Теоремы, доказанные для классического континуума и определенных на нем функций, разумеется, не обязаны сохраняться для более «редкого» конструк­

дискредитировать идею изучения вычислимых объектов; подобное изучение практически неизбежно приводит к понятиям конструктивного анализа, предлагающего здесь систематический и последовательный подход. Чи­ татель, придерживающийся описанной только что пози­ ции, должен, однако, привыкнуть к проводимой в этой книге более сильной, чем обычно, трактовке некоторых

предложения будут, как правило, сопровождаться необ­ ходимыми пояснениями.

Принцип Маркова (п. 6) является, пожалуй, наиме­ нее непосредственным из всех основных установок кон­ структивной математики. Поэтому представляет несом­ ненный интерес выяснение того, в какой мере может быть развит конструктивный анализ без использования этого принципа. В первоначальном варианте книги все приме­ нения принципа Маркова были прослежены; при этом оказалось, что основные разделы анализа сравнительно мало от него зависят. Фактически при отказе от прин­ ципа Маркова теряется всего один (правда, чрезвычайно сильный) результат, — именно, теорема непрерывности. Вместе с тем применение принципа Маркова, не выводя за рамки потенциальной осуществимости, позволяет сильно упростить многие формулировки и доказатель­

будет применяться свободно и часто без специальных оговорок.

Поскольку предлагаемая книга должна служить пер­ вому знакомству с предметом, мы отобрали наиболее элементарный, устоявшийся материал конструктивного анализа (ряд интересных работ, посвященных более да­ леким разделам математики, уже упоминался в конце п. 2). Этими же соображениями определялась и выбран­ ная нами степень подробности изложения. Мы почти ни­ когда строго не строим нормальных алгорифмов. Такие построения, чаще всего без труда выполняемые с по­

лее существенных вопросов. Характер рассматриваемых алгорифмов поясняется либо с помощью указания их свойств, либо просто описанием того, что нужно делать с исходными данными, чтобы получить искомый резуль­ тат (в такой ситуации иногда даже не вводятся обозна­ чения для излагаемого алгорифма). Внимательный чи­ татель, во всяком случае, всегда сможет без труда сопо­ ставить нашим описаниям алгорифмы в интуитивном смысле слова.

Предполагается лишь, что читатель имеет самые элемен­ тарные навыки в обращении с логическими связками и кванторами и умеет с их помощью выражать стандарт­ ные языковые формы (см., например, У с п е н с к и й [3; § 3]). Необходимые сведения из теории нормальных ал­ горифмов и перечислимых множеств в сжатой форме

курсов значительно улучшило бы общую ориентировку читателя.

Нумерация определений, теорем и т. д. сохраняется в пределах каждого параграфа; при ссылках внутри дан­ ного раздела указание на этот раздел опускается. Не­ которые фрагменты текста, на которые предполагается ссылаться в дальнейшем, выделяются посредством за­ ключенных в круглые скобки цифр. Нумерация формул и фрагментов текста сквозная в пределах каждого па­ раграфа.

Г Л А В А 1

НОРМАЛЬНЫЕ АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

из теории нормальных алгорифмов и алгорифмически пе­ речислимых множеств. Для более глубокого изучения

§1. Нормальные алгорифмы

1.Как уже отмечалось во введении, в большинстве случаев в качестве изучаемых конструктивных объектов фигурируют слова в том или ином алфавите. Напомним

таются равными, если всякая буква первого алфавита принадлежит второму и наоборот. Алфавит Б называет­ ся расширением алфавита Л, если всякая буква А при­ надлежит Б. Естественным образом определяется объе­ динение A U Б произвольных алфавитов А и Б. А [) Б состоит из тех и только тех букв, которые принадлежат А или Б. Точно так же, аналогично одноименным теоре­ тико-множественным операциям, можно определить пе­

не имеющие букв. Однако в дальнейшем всюду, где специально не оговорено противное, мы предполагаем рассматриваемые алфавиты непустыми,

Применительно к словам общее интуитивное понятие алгорифма переходит в понятие алгорифма в данном ал­ фавите. Именно, под алгорифмом в данном алфавите А

мы понимаем точное предписание, определяющее дис­ кретный детерминированный процесс преобразования слов в этом алфавите, допускающий в качестве исход­ ных данных произвольные слова в Л и дающий в каче­ стве результатов (разумеется, в тех случаях, когда соот­ ветствующий процесс оканчивается) также слова в Л. Упомянутое предписание должно обладать характерны­

расплывчатой интуитивной концепции «алгорифма в дан­ ном алфавите».

Условимся о некоторых обозначениях.

Если 21 — алгорифм в алфавите А, Р — слово в этом алфавите и процесс применения алгорифма 21 к слову Р заканчивается, то мы пишем !?l (Р) . Результат работы в этом случае обозначается через 2t(P). Таким образом, запись

21 (P) = Q

(или

Q=p3l(P))

выражает то обстоятельство, что Q является результа­ том работы алгорифма 21 над словом Р. В этой ситуации мы будем также говорить, что 21 перерабатывает слово Р в слово Q.

Мы будем использовать также знак условного ра­ венства «~»: два выражения, соединенные этим знаком, означают одно и то же слово, если хотя бы одно из них имеет смысл. Таким образом, запись

2t(P)~93(Q)

выражает то обстоятельство, что !2t(P) равносильно !23(Q) и в случае выполнения хотя бы одного из этих ус­ ловий алгорифмы 21 и 33 дают одинаковый результат на словах Р и Q.