Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Г Л А В А 1

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

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

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

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

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

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